Volume 17, No 5, 2010, P. 22-36

UDC 519.17
A. O. Ivanova
List 2-distance (Δ + 1)-coloring of planar graphs with girth at least 7

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$. There are graphs with arbitrarily large $\Delta$ and girth $g\le6$ having $\chi_2(G)\ge\Delta+2$. In the paper are improved previously known restrictions on $\Delta$ and $g$ under which every planar graph $G$ has $\chi_2(G)=\Delta+1$.
Ill. 2, bibliogr. 24.

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

Ivanova Anna Olegovna ¹
1. Institute of Mathematics at Yakutsk State University,
58 Belinskii str., 677891 Yakutsk, Russia
e-mail: shmganna@mail.ru