Geodesic
Acyclic 4-coloring of plane graphs without cycles of length~4 and~6
Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 6, pp. 3-11.

Voir la notice de l'article provenant de la source Math-Net.Ru

Every planar graph is known to be acyclically 5-colorable (Borodin, 1976), which bound is precise. Some sufficient conditions are also obtained for a planar graph to be acyclically 4-colorable. In particular, the acyclic 4-colorability was proved for the following planar graphs: without 3- and 4-cycles (Borodin, Kostochka and Woodall, 1999), without 4-, 5- and 6-cycles, (Montassier, Raspaud and Wang, 2006), without 4-, 6- and 7-cycles, and without 4-, 6- and 8-cycles (Chen, Raspaud, and Wang, 2009). In this paper it is proved that each planar graph without 4- and 6-cycles is acyclically 4-colorable. Bibl. 17.
Keywords: planar graph, acyclically coloring, acyclic choosability. 
@article{DA_2009_16_6_a0,
     author = {O. V. Borodin},
     title = {Acyclic 4-coloring of plane graphs without cycles of length~4 and~6},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--11},
     publisher = {mathdoc},
     volume = {16},
     number = {6},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2009_16_6_a0/}
}
TY  - JOUR
AU  - O. V. Borodin
TI  - Acyclic 4-coloring of plane graphs without cycles of length~4 and~6
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2009
SP  - 3
EP  - 11
VL  - 16
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2009_16_6_a0/
LA  - ru
ID  - DA_2009_16_6_a0
ER  - 
%0 Journal Article
%A O. V. Borodin
%T Acyclic 4-coloring of plane graphs without cycles of length~4 and~6
%J Diskretnyj analiz i issledovanie operacij
%D 2009
%P 3-11
%V 16
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2009_16_6_a0/
%G ru
%F DA_2009_16_6_a0
O. V. Borodin. Acyclic 4-coloring of plane graphs without cycles of length~4 and~6. Diskretnyj analiz i issledovanie operacij, Tome 16 (2009) no. 6, pp. 3-11. http://geodesic.mathdoc.fr/item/DA_2009_16_6_a0/

[1] Borodin O. V., “Dokazatelstvo gipotezy B. Gryunbauma ob atsiklicheskoi 5-raskrashivaemosti ploskikh grafov”, Dokl. AN SSSR, 231 (1976), 18–20 | MR | Zbl

[2] Borodin O. V., “Atsiklicheskaya predpisannaya 3-raskrashivaemost ploskikh grafov, ne soderzhaschikh tsiklov dliny ot 4 do 12”, Diskret. analiz i issl. operatsii, 16:5 (2009), 26–32 | MR

[3] Kostochka A. V., “Atsiklicheskaya 6-raskraska ploskikh grafov”, Metody diskret. analiza, 28, 1976, 40–56

[4] Abbott H. L., Zhou B., “On small faces in 4-critical graphs”, Ars Combinatoria, 32 (1991), 203–207 | MR | Zbl

[5] Albertson M. O., Berman D., “Every planar graph has an acyclic 7-coloring”, Israel J. Math., 28 (1977), 169–177 | DOI | MR

[6] Borodin O. V., “On acyclic colorings of planar graphs”, Discrete Math., 25 (1979), 211–236 | DOI | MR | Zbl

[7] Borodin O. V., Kostochka A. V., Woodall D. R., “Acyclic colorings of planar graphs with large girth”, J. London Math. Soc., 60 (1999), 344–352 | DOI | MR | Zbl

[8] Borodin O. V., Glebov A. N., Raspaud A., Salavatipour M. R., “Planar graphs without cycles of length from 4 to 7 are 3-colorable”, J. Combin. Theory Ser. B, 93 (2005), 303–311 | DOI | MR | Zbl

[9] Grötzsch H., “Ein Dreifarbenzatz für dreikreisfreie Netze auf der Kugel”, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Nat. Reihe, 8 (1959), 109–120 | MR

[10] Grünbaum B., “Acyclic colorings of planar graphs”, Israe J. Math., 14:3 (1973), 390–408 | DOI | MR | Zbl

[11] Hell P., Nešetřil J., Graphs and homomorphisms, Oxford Lect. Ser. Math. Appl., 28, Oxford Univ. Press, Oxford, 2004, 244 pp. | MR | Zbl

[12] Jensen T. R., Toft B., Graph coloring problems, Wiley Interscience, New York, 1995, 245 pp. | MR

[13] Kostochka A. V., Mel'nikov L. S., “Note to the paper of Grünbaum on acyclic colorings”, Discrete Math., 14 (1976), 403–406 | DOI | MR | Zbl

[14] Mitchem J., “Every planar graph has an acyclic 8-coloring”, Duke Math. J., 14 (1974), 177–181 | DOI | MR

[15] Montassier M., Raspaud A., Wang W., “Acyclic 4-choosability of planar graphs without cycles of specific lengths”, Topics in discrete mathematics, Algorithms Combin., 26, Springer-Verl., Berlin, 2006, 473–491 | MR | Zbl

[16] Montassier M., Raspaud A., Wang W., “Acyclic 5-choosability of planar graphs without small cycles”, J. Graph Theory, 54 (2007), 245–260 | DOI | MR | Zbl

[17] Steinberg R., “The state of the three color problem”, Quo Vadis, Graph Theory?, Ann. Discrete Math., 55, 1993, 211–248 | MR | Zbl