2-distance 4-coloring of planar subcubic graphs
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 2, pp. 18-28
Voir la notice de l'article provenant de la source Math-Net.Ru
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.
@article{DA_2011_18_2_a1,
author = {O. V. Borodin and A. O. Ivanova},
title = {2-distance 4-coloring of planar subcubic graphs},
journal = {Diskretnyj analiz i issledovanie operacij},
pages = {18--28},
publisher = {mathdoc},
volume = {18},
number = {2},
year = {2011},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/DA_2011_18_2_a1/}
}
O. V. Borodin; A. O. Ivanova. 2-distance 4-coloring of planar subcubic graphs. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 2, pp. 18-28. http://geodesic.mathdoc.fr/item/DA_2011_18_2_a1/