Geodesic
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/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
TI  - 2-distance 4-coloring of planar subcubic graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 18
EP  - 28
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_2_a1/
LA  - ru
ID  - DA_2011_18_2_a1
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%T 2-distance 4-coloring of planar subcubic graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 18-28
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_2_a1/
%G ru
%F 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/