Volume 17, No 5, 2010, P. 2236
UDC 519.17
A. O. Ivanova
List 2distance (Δ + 1)coloring of planar graphs with girth at least 7
Abstract:
A trivial lower bound for the 2distance 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, 2distance coloring, list coloring.
Ivanova Anna Olegovna ^{1}
1. Institute of Mathematics at Yakutsk State University,
58 Belinskii str., 677891 Yakutsk, Russia
email: shmganna@mail.ru
