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/

[1] Borodin V., Brusma Kh., Glebov A. N., Van-Den-Khoivel Ya., “Stroenie ploskikh triangulyatsii v terminakh puchkov i zvëzd”, Diskret. analiz i issled. operatsii. Ser. 1, 8:2 (2001), 15–39 | MR | Zbl

[2] Borodin O. V., Brusma Kh., Glebov A. N., Van-Den-Khoivel Ya., “Minimalnaya stepen i khromaticheskoe chislo kvadrata ploskogo grafa”, Diskret. analiz i issled. operatsii. Ser. 1, 8:4 (2001), 9–33 | MR | Zbl

[3] Borodin O. V., Ivanova A. O., Neustroeva T. K., “2-distantsionnaya raskraska razrezhennykh ploskikh grafov”, Sib. elektron. mat. izv., 1 (2004), 76–90 http://semr.math.nsc.ru/ | MR | Zbl

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

[5] Borodin O. V., Ivanova A. O., Neustroeva T. K., “Dostatochnye usloviya minimalnoi 2-distantsionnoi raskrashivaemosti ploskikh grafov s obkhvatom 6”, Sib. elektron. mat. izv., 3 (2006), 441–450 http://semr.math.nsc.ru/ | Zbl

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

[7] Ivanova A. O., “Predpisannaya 2-distantsionnaya $(\Delta+1)$-raskraska ploskikh grafov s obkhvatom ne menee 7”, Diskret. analiz i issled. operatsii, 17:5 (2010), 22–36 | MR

[8] Ivanova A. O., Soloveva A. S., “2-Distantsionnaya $(\Delta +2)$-raskraska razrezhennykh ploskikh grafov s $\Delta=3$”, Mat. zametki YaGU, 16:2 (2009), 32–41

[9] Agnarsson G., Halldorsson M. M., “Coloring powers of planar graphs”, Proc. 11th annual ACM-SIAM symposium on discrete algorithms (San Francisco, CA, 2000), ACM Press, New York, 2000, 654–662 | MR | Zbl

[10] Agnarsson G., Halldorsson M. M., “Coloring powers of planar graphs”, SIAM J. Discrete Math., 16:4 (2003), 651–662 | DOI | MR | Zbl

[11] Borodin O. V., Ivanova A. O., “2-Distance $(\Delta+2)$-coloring of planar graphs with girth six and $\Delta\ge18$”, Discrete Math., 309 (2009), 6496–6502 | DOI | MR | Zbl

[12] Borodin O. V., Ivanova A. O., “List 2-distance $(\Delta+2)$-coloring of planar graphs with girth six”, Europ. J. Combin., 30 (2009), 1257–1262 | DOI | MR | Zbl

[13] Dvořák Z., Kràl D., Nejedlỳ P., Škrekovski R., “Coloring squares of planar graphs with girth six”, Europ. J. Combin., 29:4 (2008), 838–849 | DOI | MR | Zbl

[14] Dvořák Z., Škrekovski R., Tancer M., “List-coloring squares of sparse subcubic graphs”, SIAM J. Discrete Math., 22:1 (2008), 139–159 | DOI | MR | Zbl

[15] Havet F., “Choosability of square of planar subcubic graphs with large girth”, Discrete Math., 309 (2009), 3353–3563 | DOI | MR

[16] Jensen T., Toft B., Graph coloring problems, Wiley-interscience series on discrete mathematics and optimization. A Wiley-interscience publication, John Willey Sons, New York, 1995, XXII+295 pp. | MR | Zbl

[17] Molloy M., Salavatipour M. R., “m Frequency channel assignment on planar networks”, Proc. ESA' 02, Lect. Notes Comput. Sci., 2461, Springer-Verl., London, 2002, 736–747 | MR | Zbl

[18] Molloy M., Salavatipour M. R., “A bound on the chromatic number of the square of a planar graph”, J. Combin. Theory Ser. B, 94 (2005), 189–213 | DOI | MR | Zbl

[19] Montassier M., Raspaud A., “A note on 2-facial coloring of plane graphs”, Inform. Process. Lett., 98:6 (2006), 235–241 | DOI | MR | Zbl

[20] Wegner G., Graphs with given diameter and a coloring problem, Technical Report, University of Dortmund, Dortmund, 1977