Open Journal of Discrete Mathematics
Vol.07 No.04(2017), Article ID:79024,15 pages
10.4236/ojdm.2017.74017
d-Distance Coloring of Generalized Petersen Graphs P(n, k)
Ramy Shaheen, Ziad Kanaya, Samar Jakhlab
Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
Copyright © 2017 by authors and Scientific Research Publishing Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
Received: July 18, 2017; Accepted: September 10, 2017; Published: September 13, 2017
ABSTRACT
A coloring of G is d-distance if any two vertices at distance at most d from each other get different colors. The minimum number of colors in d-distance colorings of G is its d-distance chromatic number, denoted by χd(G). In this paper, we give the exact value of cd(G) (d = 1, 2), for some types of generalized Petersen graphs P(n, k) where k = 1, 2, 3 and arbitrary n.
Keywords:
Distance Coloring, Generalized Petersen Graphs
1. Introduction
Let G = (V, E) be simple graph. A vertex k-coloring of G is a mapping from V(G) to the set such that any two adjacent vertices are mapped to different integers. The smallest integer k for which a k-coloring exists is called the chromatic number of G, denoted by c(G). The d-distance between two distinct vertices u and v, d(u, v) is the number of edges of the shortest path joining them. The d-distance k-coloring, also called distance (d, k)-coloring, is a k-coloring of the graph G, that is, any two vertices within distance d in G receive different colors. The d-distance chromatic number of G is exactly the chromatic number of G under the d-distance condition, denoted by cd(G). For a simple graph G, the dth power of G, (Gd of G) is defined such that and two vertices u and v are adjacent in Gd if and only if the distance between u and v in G is at most d. Clearly, the following inequality is holds:
The theory of plane graph coloring has a long history, extending back to the middle of the 19thcentury. In 1969, Florica Kramer and Horst Kramer [1] [2] defined the chromatic number relative to distance d of a graph G(V, E) to be the minimum number of colors which are sufficient for coloring the vertices of G in such a way that any two vertices of G of distance not greater than d have distinct colors. In 1977, Wegner [3] , studied the problem of distance coloring of planar graphs. Alon and Mohar [4] considered the maximum possible chromatic number of G2, as G ranges over all graphs with maximum degree d and girth g. Bonamy et al. [5] , studied the 2-distance coloring of sparse graphs. They proved that every graph with maximum degree Δ at least 4 and maximum average degree less that 7/3 admits a 2-distance (Δ + 1)-coloring. Okamoto and Zhang [6] , considered the 2-distance chromatic number of graphs when deleted an edge or a vertex. In [7] , Jacko gave the exact value of cd(G) of hexagonal lattice graph when d is odd and some value when d is even. Borodin and Ivanova [8] , proved that every planar graph with g ≥ 6 and ∆ ≥ 18 is (∆ + 2)-colorable. Dantas et al. [9] , studied the total coloring of generalized Petersen graphs and shown that “almost all” generalized Petersen graphs have a total chromatic number 4. Miao and Fan, [10] , gave an upper bound of the chromatic number cd(G). Many papers have been devoted to it during the last decade, see for example [11] [12] [13] [14] [15] .
In this paper, all graphs are finite, simple and undirected. For a graph G, we denote by V(G), E(G), d(u,v), ∆(G), diam(G), Gd and its vertex set, edge set, the distance between u and v which is the length of shortest path connecting them, the maximum vertex degree, the diameter of G, the power of G and d-distance coloring of G.
Theorem 1.1. [1] : For a graph we have if and only if the graph G is satisfying one of the following conditions:
1) .
2) G is a path of length greater than d.
3) G is a cycle of length a multiple of (d + 1). □
Theorem 1.2. [10] : When , there exist only two connected graphs of order n:
The path and the cycle :
1). .
2).
Theorem 1.3. [10] : Let G be a graph. Then
□
Lemma 1.1. [6] : Let G be a nontrivial graph and d a positive integer.
1) If H a subgraph of G, then .
2) equals the order of G if and only if G is connected and . □
Definition 1.1. [9] : For integers n and k with . The Generalized Petersen Graph has vertices and respectively Edges given by:
,
□
We will call (respectively ) the outer (respectively inner) subgraph of . Note that we take the skip , because of the obvious isomorphism .
2. Main Results
Our main results here are to establish the exact chromatic number (d = 1, 2) for k = 1, 2, 3 and arbitrary n.
Theorem 2.1.
Proof. Let , observe from Definition 1.1, that Generalized Petersen Graphs composed of one outer cycle and several inner cycles dependent on k. So, when k = 1 there is one inner cycle, then G composed of two cycles of size n. There are two cases:
Case 1: n is even, immediately from Theorem 1.1 we have (because d = 1) then
(1)
We define a function f with colors in the set {1, 2} for ai and bi as follows:
,
Then
(2)
By (1) and (2) we get .
Case 2: n is odd, from Theorem 1.2, we have . Then
(3)
We define a function f with colors in the set {1, 2, 3} for ai and bi as follows:
So,
. (4)
From (3) and (4), gets . As example see Figure 1.
Theorem 2.2:
Proof. Let . We have is an induced subgraph of G and from Theorem 1.2, gets . So,
(5)
We define a function f with colors in the set for ai and bi as follows:
, , , .
By follow-up the coloring to the right, for there is only a single color as .
So, for each vertex there is only a single color:
, , , ,
, , .
Observe that we have a repeat of the same order of the colors for each 4-inner (4-outer) vertices. Consider G with . Assume that : for each we define a subset of V(G) by then there is a function f with colors in the set define as follows:
,
We have four cases according to the value of n modulo 4:
Case 1: r = 0. Then . By function f is
(6)
From (5) and (6), we get .
Figure 1. .
Case 2: r = 1. There are two leftover vertices in . By function f we have , which is a contradiction with and . Moreover . So, each of and needs deferent color then . We define , where is a function with colors in the set {3, 4, 5} define as follows:
Then we get = when .
Case 3: For r = 2, we have two subcases:
Case 3.1: r = 2 and n > 6, a similar argument, there is a contradiction for , , , . Then, . We define
is a function with colors in the set define as follows:
Then we get when , see Figure 2.
Case 3.2: r = 2 and n = 6. There are two cycles of order 6 and know that . Without loss of generality, assuming that . Then the vertices a2, a3, a5, a6, b1, b2, b6, can’t take the color 1. Moreover, at most one of a4, b3, b4, b5 can be coloring by 1. This implies that each color has only two vertices from . So, needs 6 colors for 12 vertices. Furthermore, .
Case 4: For r = 3, there are two subcases:
Case 4.1: n ≥ 7. For a function coloring f there is a contradiction in and . Then . We define
Figure 2. .
where is a function with colors in the set define as follows:
Then, when .
Case 4.2: n = 3. Then, . By Lemma 1.1, we get . □
Theorem 2.3: .
Proof: Let . We have is an induced subgraph of G. Then by Theorem 1.2, is . So,
(7)
We define a function f as follows:
,
We have three cases according to the value of n modulo 3:
Case 1: r = 0. By definition f we have
(8)
By (7) together with (8), gets when .
Case 2: r = 1. Then there is a contradiction for . We define
where . This implies that when .
Case 3: r = 2. There is a problem with colors the vertices .
We define , where is a function with colors in the set define as follows:
By the last result together with (7), we get when . □
Theorem 2.4:
Proof: Let . G including as an induced subgraph. We have . Then by Lemma 1.1, we get . Furthermore
(9)
We define a function f with colors in the set for and as follows:
, , , ,
Then for there are two cases:
Case a: . (By coloring to the right). So, has only a single color as and . Follow-up coloring inner (outer) vertices each vertex will have only a single color as follows:
, , , , , ,
, , , , ,
By continue we will have a repeat of the same order of the colors for each 10-inner (10-outer) vertices.
Case b: . By coloring to the left. So, we back to consider the Case 1.
We will consider G with . Assume that : . Now, for each we define a subset of V(G) by
Then there is a function f define as follows:
,
We have ten cases according to the value of n modulo 10:
Case 1: r = 0. Then . Moreover, by define f we have
(10)
From (9) and (10) we get when .
Case 2: r = 1. There are two leftover vertices in . By function f, , which is a contradiction with and , and . So each of and needs deferent color then . We define
where is a function with colors in the set define as follows:
Then we get when .
Case 3: r = 2. There are four leftover vertices in , which are a contradiction with . This implies that .
Let
where is a function with colors in the set define as follows:
Then when . See Figure 3.
Case 4: r = 3. By same argument there is a contradiction for . Which implies that . So, we define
where that is a function with colors in the set define as follows:
Then we get when .
Case 5: r = 4. There is a contradiction for . We define
where is a function with colors in the set define as follows:
We get when .
Case 6: When r = 5 we have two subcases:
Case 6.1: r = 5 and . The contradiction is for . We will need at least three new deferent colors for them, then . We define
Figure 3. .
where is a function with colors in the set define as follows:
Then when . See Figure 4.
Case 6. 2: r = 5 and n = 5. We have diam(G) = 2. So, Lemma 1.1, gets .
Case 7: r = 6. A contradiction for , . We define and is a function with color 6. So, , gets when .
Notice when n = 6 we have the same argument but , so the vertices will take the sequence of colors for (outer, inner)vertices as follows (1, 2, 3, 1, 2, 3, 4, 4, 5, 5, 6, 6).
Case 8: r = 7. A contradiction is only for . Let . Where . Moreover, when . Also when n = 7 we get by the same condition with sequence of colors (outer, inner) vertices as following (1, 2, 3, 1, 4, 3, 5, 6, 4, 5, 5, 2, 2, 6).
Case 9: r = 8. A contradiction is for , , , then . We define with is a function with colors in the set define as follows:
Figure 4. .
And so, gets when .
Also notice when n = 8 we have the same argument but , so the vertices will take the sequence of colors for (outer, inner) vertices as follows (1, 2, 3, 1, 6, 4, 5, 6, 4, 4, 5, 5, 2, 2, 3, 3).
Case 10: r = 9. There is a contradiction for , , then . Let us define , with is a function with colors in the set define as follows:
Furthermore, when .
As before when n = 9 we get , by the same condition with sequence of colors (outer, inner) vertices as follows (1, 2, 3, 1, 6, 3, 4, 5, 3, 4, 4, 5, 5, 2, 2, 1, 6, 6).
Finally, we conclude that:
Theorem 2.5:
Proof. Let . There are two cases:
Case 1: . From Theorem 1.2, we have . Then
(11)
We define a function f with colors in the set {1, 2} for and ( ),
,
Then
(12)
From (11) and (12), gets .
Case 2: . From Theorem 1.2, we have . Moreover,
(13)
Let for and , where
Then
. (14)
From (13) and (14) is . □
Theorem 2.6:
Proof. Let . is an induced subgraph of G and . This implies that
. (15)
Without loss of generality, we define a function f as follows: , , , . By follow-up the coloring to the right, for there are two cases or .
Case 1: . Then, there are two cases for , or . So, if then absolutely and . For coloring we need another color because it has the four colors as neighbors. If , then and . Furthermore, for coloring we need another color. So to avoiding the fifth color we have to take the second case.
Case 2: . There are two cases for , or , we have two subcases:
Case 2.1: . Absolutely and or . If we take then , , but we need another color for . Also if we take then we need new color for .
Case 2.2: . For each vertex there is only a single color: , , , , , . Observe that, we have a repeat of the same order of the colors for each (4-outer) and (4-inner) vertices as respectively for colors and . Consider G with . Assume that : for each , we define a subset of V(G) by then there is a function f define as follows:
,
We have four cases according to the value of n modulo 4:
Case 2.2.1: r = 0. Then . By function f we have
(16)
From (15) and (16) we get .
Case 2.2.2: r = 1. Then there are two leftover vertices in , by function f we get , which is a contradiction with and . So each of and needs deferent color then . We define
where is a function with colors in the set {2, 3, 4, 5} define as follows:
Then gets when .
Case 2.2.3: r = 2. Here, we will consider , {we delete the details of the general case because they are too long}.
We have . Suppose . It is easy to prove that each color can be given at most to four vertices. This implies that each color has exactly four vertices. {If drawing as following form: (outer cycle, inner cycle) respectively, , such that we gets the same graph ( , i.e., }. Furthermore, no more three vertices from (outer cycle, inner cycle) respectively, can be take the same color.
Assume that there are five sets of colors, D1, D2, D3, D4, D5, i.e., f(v) = i if and only ( ). We will study the cases for one of Di. If Di contain r vertices of outer cycle and q vertices of inner cycle, then we called Di is (r-outer, q-inner). Without loss of generality, we consider D1. Thus, we distinguish two cases:
Case a: D1 is (3-outer, 1-inner).
(This Case is similar by symmetry to D1 is (1-outer, 3-inner).
Let’s start with then we have (up to isomorphism) , , and . Thus, or and or . We have two cases:
Case a.1: and or and . Two cases are similar by symmetry. Let and . Then , , , , . Then , a contradiction with our hypothesis, .
Case a.2: and are belonging to the same set, let . There are two subcases or :
Case a.2.1: . Then , , , , , , . So, , a contradiction with .
Case a.2.2: . Then , . This implies that , again gets a contradiction with .
Case b: D1 is (2-outer, 2-inner).
Assume that . We have three cases to choose the second vertex from outer cycle.
Case b.1: . (We have the same result if we take ). Just one of , can belongs to . So, has three vertices and that means a contradiction with our proof that each set is from size 4.
Case b.2: . (We have the same result if we take ). Then , , , , . Also, or .
Case b.2.1: . Then , , , , , , . Thus, , a contradiction with .
Case b.2.2: . Then , , , , . Thus, we get , a contradiction with .
Case b.3: . Then no vertex in inner cycle can take the color 1. We get a contradiction with our proof that each set is from size 4.
Finally, we conclude that . To prove that , we take a function as follows:
Then we get when . See Figure 5.
Case 2.2.4: r = 3. we have two subcases:
Case 2.2.4.1: r = 3 and n > 7. The contradiction in , , and . We define
where is a function with colors in the set {4, 5}, define as follows:
Figure 5. .
Then we get when for n > 7.
Case 2.2.4.2: r = 3 and n = 7. In this case we have
induced subgraph from
. Furthermore,
. Let take the cycle
and give it the fife color as follows:
Case 2.2.4.2.a: . Then for we have two choices 1 or 5. For the first choice we get , , . But for there are two colors 2 or 5. If , then we will need a new color for . Also, if then . Obviously, we need a new color for . For second choice then or . If we have for two colors 2 or 3 if we take the color 2 then needs a new color for the vertices . Also, if we take the color 3 we will need a new color for because can only take the color 2. If then , , . Moreover, we will need a new color for .
Case 2.2.4.2.b:
then for
we have two choices 1 or 4. For
we get
,
,
,
, , ,
, , .
Finally, we get .
Acknowledgements
The authors would like to thank the referees for their careful reading of the paper and their helpful comments.
Cite this paper
Shaheen, R., Kanaya, Z. and Jakhlab, S. (2017) d-Distance Coloring of Generalized Petersen Graphs P(n, k). Open Journal of Discrete Mathematics, 7, 185-199. https://doi.org/10.4236/ojdm.2017.74017
References
- 1. Kramer, F. and Kramer, H. (1969) Un probleme de coloration des sommets d’un graphe. C. R. Acad. Sci. Paris A, 268, 46-48.
- 2. Kramer, F. and Kramer, H. (1969) Ein Fäbungsproblem der Knotenpunkte eines Graphen bezülich der Distanz p. Rev. Roumaine Math. Pures Appl., 14, 1031-1038.
- 3. Wegner, G. (1977) Graphs with Given Diameter and a Coloring Problem. Technical Report, University of Dortmond, Dortmond, Germany.
- 4. Alon, N. and Mohar, B. (2002) The Chromatic Number of Graph Powers. Combinatorics, Probability and Computing, 11, 1-10. https://doi.org/10.1017/S0963548301004965
- 5. Bonamy, M., Lévêque, B. and Pinlou, A. (2011) 2-Distance Coloring of Sparse Graphs. Electronic Notes in Discrete Mathematics, 38, 155-160. https://doi.org/10.1016/j.endm.2011.09.027
- 6. Okamoto, F. and Zhang, P. (2010) A Note on 2-Distance Chromatic Numbers of Graphs. AKCE J. Graphs. Combin, 7, 5-9.
- 7. Jacko, P. and Jendrol, S. (2005) Distance Coloring of the Hexagonal Lattice. Discussiones Mathematicae Graph Theory, 25, 1-xxx. https://doi.org/10.7151/dmgt.1269
- 8. Borodin, O.V. and Ivanova, A.O. (2009) 2-Distance (Δ + 2)-Coloring of Planar Graphs with Girth Six and Δ ≥ 18. Discrete Mathematics, 309, 6496-6502. https://doi.org/10.1016/j.disc.2009.06.029
- 9. Dantas, S., de Figueiredo, C.M.H., Mazzuoccoloc, G., Preissmann, M., dos Santos, V.F. and Sasaki, D. (2016) On the Total Coloring of Generalized Petersen Graphs. Discrete Mathematics, 339, 1471-1475. https://doi.org/10.1016/j.disc.2015.12.010
- 10. Miao, L. and Fan, Y. (2014) The Distance Coloring of Graphs. Acta Mathematica Sinica, English Series, 30, 1579-1587. https://doi.org/10.1007/s10114-014-3238-9
- 11. Havet, F., van den Heuvel, J., McDiarmid, C. and Reed, B. (2007) List Colouring Squares of Planar Graphs. Electronic Notes in Discrete Mathematics, 29, 515-519.
- 12. Ito, T., Kato, A., Zhou, X. and Nishizeki, T. (2007) Algorithms for Finding Distance-Edge-Colorings of Graphs. Journal of Discrete Algorithms, 5, 304-322.
- 13. Kramer, F. and Kramer, H. (2008) A Survey on the Distance-Colouring of Graphs. Discrete Mathematics, 308, 422-426.
- 14. Borodin, O.V. (2013) Colorings of Plane Graphs: A Survey. Discrete Mathematics, 313, 517-539.
- 15. Shao, Z. and Vesel, A. (2013) A Note on the Chromatic Number of the Square of the Cartesian Product of Two Cycles. Discrete Mathematics, 313, 999-1001.