Volume 18, No 2, 2011, P. 18-28

UDC 519.17
O. V. Borodin, A. O. Ivanova
2-distance 4-coloring of planar subcubic graphs

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.

Keywords: planar graph, 2-distance coloring, subcubic graph.

Borodin Oleg Veniaminovich ^1,2
Ivanova Anna Olegovna ³
1. S. L. Sobolev Institute of Mathematics, SB RAS,
4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
3. Institute of Mathematics at Yakutsk State University, Yakutsk State University,
48 Kulakovskogo str., 677891 Yakutsk, Russia
e-mail: brdnoleg@math.nsc.ru, shmgnanna@mail.ru