Geodesic
Acyclic 4-colorability of planar graphs without 4- and 5-cycles
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 2, pp. 20-38.

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

[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 issled. operatsii, 16:5 (2009), 26–33 | MR

[3] Borodin O. V., “Atsiklicheskaya 4-raskrashivaemost ploskikh grafov bez tsiklov dliny 4 i 6”, Diskret. analiz i issled. operatsii, 16:6 (2009), 3–11

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

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

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

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

[8] Borodin O. V., “To the paper of H. L. Abbott and B. Zhou on 4-critical planar graphs”, Ars Comb., 43 (1996), 191–192 | MR | Zbl

[9] Borodin O. V., “Structural properties of plane graphs without adjacent triangles and an application to 3-colorings”, J. Graph Theory, 21:2 (1996), 183–186 | 3.0.CO;2-N class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[10] 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

[11] 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. Comb. Theory Ser. B, 93 (2005), 303–311 | DOI | MR | Zbl

[12] Borodin O. V., Glebov A. N., Montassier M., Raspaud A., “Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable”, J. Comb. Theory Ser. B, 99 (2009), 668–673 | DOI | MR | Zbl

[13] Hell P., Nešetřil J., Graphs and homomorphisms, Oxford Lecture Series in Mathematics and its Applications, 28, Oxford Univ. Press, Oxford, 2004, 244 pp. | MR | Zbl

[14] Hocquard H., Montassier M., “Every planar graph without cycles of lengths 4 to 12 is acyclically 3-choosable”, Inf. Process. Lett., 109:21–22 (2009), 1193–1196 | DOI | MR

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

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

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

[18] 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

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

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

[21] Sanders D. P., Zhao Y., “A note on the three color problem”, Graphs Comb., 11 (1995), 91–94 | DOI | MR | Zbl

[22] Steinberg R., “The state of the three color problem”, Quo Vadis, Graph Theory?, Ann. Discrete Math., 55, eds. J. Gimbel, J. W. Kennedy, L. V. Quintas, 1993, 211–248 | MR | Zbl

[23] Xu B., “On 3-colorable plane graphs without 5- and 7-cycles”, J. Comb. Theory Ser. B, 96 (2006), 958–963 | DOI | MR | Zbl