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-distancechromatic 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.
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.
![\"\"](\"Edit_f10de6cf-16b2-4c5e-83a0-f60130a9472d.bmp\")
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
