A Result on the 2-Distance Coloring of Planar Graphs with Girth Five

Year 2025, Volume: 13 Issue: 1, 60 - 66, 30.04.2025

Elif Aras

Abstract

A vertex coloring of a graph $G$ is said to be a 2-distance coloring if any two vertices at distance at most $2$ from each other receive different colors, and the least number of colors for which $G$ admits a 2-distance coloring is known as the 2-distance chromatic number of $G$, and denoted by $\chi_2(G)$. We prove that if $G$ is a planar graph with girth $5$ and maximum degree $\Delta \geq 12$, then $\chi_2(G)\leq \Delta(G)+5$.

Keywords

Coloring, planar graph, girth, maximum degree

References

• [1] Bu, Y., and Zhu, X. An optimal square coloring of planar graphs, Journal of Combinatorial Optimization 24 580–592, 2012.
• [2] Bu Y, and Zhu J. Channel Assignment with r-Dynamic Coloring, 12th International Conference, AAIM 2018, Dallas, TX, USA, December 3-4, Proceedings pp 36-48, 2018.
• [3] Deniz, Z. An improved bound for 2-distance coloring of planar graphs with girth six. Discrete Applied Mathematics, 361, 121-135, 2025.
• [4] Deniz, Z. Some results on 2-distance coloring of planar graphs with girth five. Journal of Combinatorial Optimization, 47(4), 68, 2024.
• [5] Heuvel, J. van den, McGuinness, S., Coloring the square of a planar graph, Journal of Graph Theory, 42 110–124, (2003).
• [6] Jin, Y. D., and Miao, L. Y., List 2-distance Coloring of Planar Graphs with Girth Five. Acta Mathematicae Applicatae Sinica, English Series, 38(3), 540-548, (2022).
• [7] La, H. 2-distance list (D+3)-coloring of sparse graphs. Graphs and Combinatorics, 38(6), 167, 2022.
• [8] Molloy, M. and Salavatipour, M. R., A bound on the chromatic number of the square of a planar graph, Journal of Combinatorial Theory Series B, 94, 189–213, (2005).
• [9] Thomassen, C., The square of a planar cubic graph is 7-colorable. Journal of Combinatorial Theory Series B, 128:192–218, (2018).
• [10] Wegner, G., Graphs with given diameter and a coloring problem. Technical report, University of Dormund, (1977).
• [11] D. B. West. Introduction to graph theory, volume 2. Prentice hall Upper Saddle River, 2001.