Abstract:
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.
Citation:
O. V. Borodin, “Acyclic 4-colorability of planar graphs without 4- and 5-cycles”, Diskretn. Anal. Issled. Oper., 17:2 (2010), 20–38; J. Appl. Industr. Math., 5:1 (2011), 31–43
This publication is cited in the following 12 articles:
Zhu E., Li Z., Shao Z., Xu J., “Construction of Acyclically 4-Colourable Planar Triangulations With Minimum Degree 4”, Int. J. Comput. Math., 96:9 (2019), 1723–1734
Zhu E. Li Z. Shao Z. Xu J., “On Acyclically 4-Colorable Maximal Planar Graphs”, Appl. Math. Comput., 329 (2018), 402–407
Zhu E., Li Z., Shao Z., Xu J., “Acyclically 4-Colorable Triangulations”, Inf. Process. Lett., 116:6 (2016), 401–408
Borodin O.V. Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs with No 4- and 5-Cycles”, J. Graph Theory, 72:4 (2013), 374–397
Borodin O.V., “Colorings of Plane Graphs: a Survey”, Discrete Math., 313:4 (2013), 517–539
Chen M. Raspaud A., “Planar Graphs Without 4-and 5-Cycles Are Acyclically 4-Choosable”, Discrete Appl. Math., 161:7-8 (2013), 921–931
Borodin O.V. Ivanova A.O., “Acyclic 4-Choosability of Planar Graphs Without Adjacent Short Cycles”, Discrete Math., 312:22 (2012), 3335–3341
Chen M. Raspaud A., “A Sufficient Condition for Planar Graphs to Be Acyclically 5-Choosable”, J. Graph Theory, 70:2 (2012), 135–151
Chen M., Raspaud A., Roussel N., Zhu X., “Acyclic 4-choosability of planar graphs”, Discrete Math., 311:1 (2011), 92–101
O. V. Borodin, A. O. Ivanova, “Acyclic 5-choosability of planar graphs without 4-cycles”, Siberian Math. J., 52:3 (2011), 411–425
Borodin O.V., Ivanova A.O., “Acyclic 5-choosability of planar graphs without adjacent short cycles”, J. Graph Theory, 68:2 (2011), 169–176
O. V. Borodin, A. O. Ivanova, “Acyclic $3$-choosability of planar graphs with no cycles of length from $4$ to $11$”, Sib. elektron. matem. izv., 7 (2010), 275–283