Acyclic 4‐Choosability of Planar Graphs with No 4‐ and 5‐Cycles
Oleg Veniaminovich Borodin, Anna O. Ivanova · Journal of Graph Theory · 2012
Abstract Every planar graph is known to be acyclically 7‐choosable and is conjectured to be acyclically 5‐choosable (O. V. Borodin, D. G. Fon‐Der‐Flaass, A. V. Kostochka, E. Sopena, J Graph Theory 40 (2002), 83–90). This conjecture if proved would imply both Borodin's (Discrete Math 25 (1979), 211–236) acyclic 5‐color theorem and Thomassen's (J Combin Theory Ser B 62 (1994), 180–181) 5‐choosability theorem. However, as yet it has been verified only for several restricted classes of graphs. Some sufficient conditions are also obtained for a planar graph to be acyclically 4‐ and 3‐choosable. In particular, the acyclic 4‐choosability was proved for the following planar graphs: without 3‐, 4‐, and 5‐cycles (M. Montassier, P. Ochem, and A. Raspaud, J Graph Theory 51 (2006), 281–300), without 4‐, 5‐, and 6‐cycles, or without 4‐, 5‐, and 7‐cycles, or without 4‐, 5‐, and intersecting 3‐cycles (M. Montassier, A. Raspaud, W. Wang, Topics Discrete Math (2006), 473–491), and neither 4‐ and 5‐cycles nor 8‐cycles having a triangular chord (M. Chen and A. Raspaud, Discrete Math. 310(15–16) (2010), 2113–2118). The purpose of this paper is to strengthen these results by proving that each planar graph without 4‐ and 5‐cycles is acyclically 4‐choosable.