Research Article
BibTex RIS Cite

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

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

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$.

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.
Year 2025, Volume: 13 Issue: 1, 60 - 66, 30.04.2025

Abstract

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.
There are 11 citations in total.

Details

Primary Language English
Subjects Applied Mathematics (Other)
Journal Section Articles
Authors

Elif Aras

Early Pub Date April 28, 2025
Publication Date April 30, 2025
Submission Date November 18, 2024
Acceptance Date April 7, 2025
Published in Issue Year 2025 Volume: 13 Issue: 1

Cite

APA Aras, E. (2025). A Result on the 2-Distance Coloring of Planar Graphs with Girth Five. Konuralp Journal of Mathematics, 13(1), 60-66.
AMA Aras E. A Result on the 2-Distance Coloring of Planar Graphs with Girth Five. Konuralp J. Math. April 2025;13(1):60-66.
Chicago Aras, Elif. “A Result on the 2-Distance Coloring of Planar Graphs With Girth Five”. Konuralp Journal of Mathematics 13, no. 1 (April 2025): 60-66.
EndNote Aras E (April 1, 2025) A Result on the 2-Distance Coloring of Planar Graphs with Girth Five. Konuralp Journal of Mathematics 13 1 60–66.
IEEE E. Aras, “A Result on the 2-Distance Coloring of Planar Graphs with Girth Five”, Konuralp J. Math., vol. 13, no. 1, pp. 60–66, 2025.
ISNAD Aras, Elif. “A Result on the 2-Distance Coloring of Planar Graphs With Girth Five”. Konuralp Journal of Mathematics 13/1 (April 2025), 60-66.
JAMA Aras E. A Result on the 2-Distance Coloring of Planar Graphs with Girth Five. Konuralp J. Math. 2025;13:60–66.
MLA Aras, Elif. “A Result on the 2-Distance Coloring of Planar Graphs With Girth Five”. Konuralp Journal of Mathematics, vol. 13, no. 1, 2025, pp. 60-66.
Vancouver Aras E. A Result on the 2-Distance Coloring of Planar Graphs with Girth Five. Konuralp J. Math. 2025;13(1):60-6.
Creative Commons License
The published articles in KJM are licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.