Abstract:
A trivial lower bound for the 2-distance chromatic number $\chi_2(G)$ of every graph $G$ with maximum degree $\Delta$ is $\Delta+1$. It is known that $\chi_2=\Delta+1$, if girth $g\ge7$ and $\Delta$ is sufficiently large. There are graphs with arbitrarily large $\Delta$ and girth $g\le6$ having $\chi_2(G)\ge\Delta+2$. In this paper the 4-colorability of planar subcubic graph with $g\ge23$ is proved, which improves the same result ($g\ge24$) by Borodin, Ivanova, and Neustroeva (2004) and by Dvořák, Škrekovski, and Tancer (2008). Ill. 2, bibliogr. 20.