Research ArticleOpen AccessGoogle Scholar indexed
<i>d-Distance</i> Coloring of Generalized Petersen Graphs <i>P(n, k)</i>
Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
- 1 Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
- 2 Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
- 3 Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria
Open Journal of Discrete Mathematics·Volume 07 (2017)·Pages 185–199·Published 12 September 2017·DOI10.4236/ojdm.2017.74017
Copy link · social · email
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 .
KeywordsDistance ColoringGeneralized Petersen Graphs
- Kramer, F. and Kramer, H. (1969) Un probleme de coloration des sommets d’un graphe. C. R. Acad. Sci. Paris A, 268, 46-48.
- 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.
- Wegner, G. (1977) Graphs with Given Diameter and a Coloring Problem. Technical Report, University of Dortmond, Dortmond, Germany.
- 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
- 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
- Okamoto, F. and Zhang, P. (2010) A Note on 2-Distance Chromatic Numbers of Graphs. AKCE J. Graphs. Combin, 7, 5-9.
- 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
- 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
- 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
- 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
- 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.
- 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.
- Kramer, F. and Kramer, H. (2008) A Survey on the Distance-Colouring of Graphs. Discrete Mathematics, 308, 422-426.
- Borodin, O.V. (2013) Colorings of Plane Graphs: A Survey. Discrete Mathematics, 313, 517-539.
- 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.