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