Abstract
A vertex coloring is called \(2\)-distance if any two vertices at distance at most \(2\) from each other get different colors. The minimum number of colors in 2-distance colorings of \(G\) is its 2-distance chromatic number, denoted by \(\chi _2(G)\). Let \(G\) be a plane graph with girth at least \(5\). In this paper, we prove that \(\chi _2(G)\le \Delta +8\) for arbitrary \(\Delta (G)\), which partially improves some known results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy JA, Murty USR (1976) Graph theory with applications. Macmillan Ltd. Press, New York
Borodin OV, Broersma H, Glebov A, van den Heuvel J (2002) Stars and bunches in planar graphs. General planar graphs and colourings. CDAM Researches Report Part II
Borodin OV, Ivanova AO (2009) 2-Distance \(\Delta +2\)-coloring of planar graphs with girth six and \(\Delta \ge 18\). Discret Math 309:6496–6502
Borodin OV, Ivanova AO, Neustroeva TK (2004) 2-Distance coloring of sparse plane graphs. Sib Èlektron Math Izv 1:76–90 (in Russian)
Borodin OV, Glebov AN, Ivanova AO, Neustroeva TK, Tashkinov VA (2004) Sufficient conditions for the 2-distance \(\Delta +1\)-colorability of plane graphs. Sib lektron Math Izv 1:129–141 (in Russian)
Bu Y, Zhu X (2012) An optimal square coloring of planar graphs. J Comb Optim 24:580–592
Bu Y, Yan X (2014) List 2-distance coloring of planar graphs. J Comb Optim doi:10.1007/s10878-013-9700-2
Charpentier C, Montassier M, Raspaud A (2013) L(p, q)-labeling of sparse graphs. J Comb Optim 25:646–660
Dvořàk Z, Kràl D, Nejedlỳ P, Škrekovski R (2008) Coloring squares of planar graphs with girth six. Eur J Comb 29:838–849
Molloy M, Salavatipour MR (2005) A bound on the chromatic number of the square of a planar graph. J Comb Theory Ser B 94:189–213
van den Heuvel J, McGuinness S (2003) Coloring of the square of planar graph. J Graph Theory 42:110–124
Wang W, Lih K (2003) Labeling planar graphs with conditions on girth and distance two. SIAM J Discret Math 17(2):264–275
Wegner G (1977) Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, Germany
Acknowledgments
The authors thank the referees for their valuable suggestions which helped to improve the presentation of this paper. The first author is supported by China Postdoctoral Science Foundation (No. 2013M531243)and Natural Science Foundation of jiangsu Province of China (No. BK20140089).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Dong, W., Lin, W. An improved bound on 2-distance coloring plane graphs with girth 5. J Comb Optim 32, 645–655 (2016). https://doi.org/10.1007/s10878-015-9888-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-015-9888-4