OJDM  Vol.7 No.4 , October 2017
d-Distance Coloring of Generalized Petersen Graphs P(n, k)
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 χd(G) (d = 1, 2), for some types of generalized Petersen graphs P(n, k) where k = 1, 2, 3 and arbitrary n.
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. doi: 10.4236/ojdm.2017.74017.

[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.

[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.

[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.

[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.

[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.

[10]   Miao, L. and Fan, Y. (2014) The Distance Coloring of Graphs. Acta Mathematica Sinica, English Series, 30, 1579-1587.

[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.