Abstract
A 2 distance k-coloring of a graph G is a function \(f: V(G)\rightarrow \{1,2,\ldots ,k\}\) such that \(|f(u)-f(v)|\ge 1\) if \(1\le d(u,v)\le 2\), where d(u, v) is the distance between the two vertices u and v. The 2-distance chromatic number of G, written \(\chi _2(G)\), is the minimum k such that G has such a coloring. In this paper, we show that \(\chi _2(G)\le 5\Delta -7\) holds for planar graphs G with maximum degree \(\Delta \ge 5\), which improves a result due to Zhu and Bu (J. Comb. Optim. 36:55–64, 2018).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agnarsson, G., Halldorsson, M.M.: Coloring powers of planar graphs. SIAM J. Discrete Math. 16, 651–662 (2003)
Borodin, O.V., Broersma, H.J., Glebov, A., Heuvel, J.V.D.: Stars and bunches in planar graphs. Part II: General planar graphs and colourings, CDAM researches report 2002-05 (2002)
Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5, 586–595 (1992)
van den Heuvel, J., McGuinness, S.M., Molloy, Salavatipour, M.: Coloring of the square of planar graph. J. Graph Theory 42, 110–124 (2003)
Molloy, M., Salavatipour, M.: A bound on the chromatic number of the square of a planar graph. J. Comb. Theory Ser. B. 94, 189–213 (2005)
Montassier, M., Raspaud, A.: A note on 2-facial coloring of plane graphs. Inf. Process. Lett. 98, 235–241 (2006)
Roberts, F.S.: T-colorings of graphs: recent results and open problems. Discrete Math. 93, 229–245 (1991)
Song, H.M., Lai, H.J.: Upper bounds of r-hued colorings of planar graphs. Discrete Appl. Math. 243, 262–269 (2018)
Thomasse, C.: Applications of Tutte cycles, Technical report, Technical University of Denmark (2001)
Wegner, G.: Graphs with given diameter and a coloring problem. Technical report, University of Dortmund (1977)
Zhu, J., Bu, Y.: Minimum 2-distance coloring of planar graphs and channel assignment. J. Comb. Optim. 36(1), 55–64 (2018). https://doi.org/10.1007/s10878-018-0285-7
Acknowledgement
This research was supported by National Science Foundation of China under Grant Nos. 11901243, 11771403 and Zhejiang Provincial Natural Science Foundation of China under Grant No. LQ19A010005.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Zhu, J., Bu, Y., Zhu, H. (2021). Wegner’s Conjecture on 2-Distance Coloring. In: Wu, W., Du, H. (eds) Algorithmic Aspects in Information and Management. AAIM 2021. Lecture Notes in Computer Science(), vol 13153. Springer, Cham. https://doi.org/10.1007/978-3-030-93176-6_34
Download citation
DOI: https://doi.org/10.1007/978-3-030-93176-6_34
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-93175-9
Online ISBN: 978-3-030-93176-6
eBook Packages: Computer ScienceComputer Science (R0)