Geodesic
Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth~$6$
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 441-450.

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 any graph $G$ with maximum degree $\Delta$ is $\Delta+1$. It is known that if $G$ is planar and its girth is at least $7$, then for large enough $\Delta$ this bound is sharp, while for girth $6$ it is not true. We prove that if $G$ is planar, its girth is $6$, every edge is incident with a $2$-vertex, and $\Delta\ge31$, then $\chi_2(G)=\Delta+1$. 
@article{SEMR_2006_3_a28,
     author = {O. V. Borodin and A. O. Ivanova and T. K. Neustroeva},
     title = {Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth~$6$},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {441--450},
     publisher = {mathdoc},
     volume = {3},
     year = {2006},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2006_3_a28/}
}
TY  - JOUR
AU  - O. V. Borodin
AU  - A. O. Ivanova
AU  - T. K. Neustroeva
TI  - Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth~$6$
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2006
SP  - 441
EP  - 450
VL  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2006_3_a28/
LA  - ru
ID  - SEMR_2006_3_a28
ER  - 
%0 Journal Article
%A O. V. Borodin
%A A. O. Ivanova
%A T. K. Neustroeva
%T Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth~$6$
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2006
%P 441-450
%V 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2006_3_a28/
%G ru
%F SEMR_2006_3_a28
O. V. Borodin; A. O. Ivanova; T. K. Neustroeva. Sufficient conditions for the minimum $2$-distance colorability of plane graphs of girth~$6$. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 3 (2006), pp. 441-450. http://geodesic.mathdoc.fr/item/SEMR_2006_3_a28/

[1] Jensen T. R., Toft B., Graph coloring problems, John Wiley Sons, New York, 1995 | MR | Zbl

[2] Borodin O. V., Glebov A. N., Ivanova A. O., Neustroeva T. K., Tashkinov V. A., “Dostatochnye usloviya 2-distantsionnoi $(\Delta+1)$-raskrashivaemosti ploskikh grafov”, Sibirskie elektronnye matematicheskie izvestiya, 1 (2004), 129–141 http://semr.math.nsc.ru/ | MR | Zbl

[3] Borodin O. V., Ivanova A. O., Neustroeva T. K., “Dostatochnye usloviya 2-distantsionnoi $(\Delta+1)$-raskrashivaemosti ploskikh grafov s obkhvatom 6”, Diskretnyi analiz i issledovanie operatsii, Seriya 1, 12:3 (iyul–sentyabr 2005), 32–47 | MR