An improved bound for 2-distance coloring of planar graphs with girth six

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 chi(2)(G) of G. When G is a planar graph with girth at least 6 and maximum degree triangle >= 6, we prove that chi(2)(G) <= triangle+4. This improves the best known bound for 2-distance coloring of planar graphs with girth six. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.