Planar graphs without 4- and 5-cycles are acyclically 4-choosable

Let G=(V,E)G=(V,E) be a graph. A proper vertex coloring of GG is acyclic if GG contains no bicolored cycle. Namely, every cycle of GG must be colored with at least three colors. GG is acyclically LL-list colorable if for a given list assignment L={L(v):v∈V}L={L(v):v∈V}, there exists a proper acyclic coloring ππ of GG such that π(v)∈L(v)π(v)∈L(v) for all v∈Vv∈V. If GG is acyclically LL-list colorable for any list assignment with |L(v)|≥k|L(v)|≥k for all v∈Vv∈V, then GG is acyclically kk-choosable.In 1976, Steinberg Jensen and Toft (1995) [20] conjectured that every planar graph without 4- and 5-cycles is 3-colorable. This conjecture cannot be improved to 3-choosability basing on the examples given by Voigt (2007) [30] and, independently, by Montassier (2005) [24]. In this paper, we prove that planar graphs without 4- and 5-cycles are acyclically 4-choosable. This result (obtained independently by Borodin and Ivanova (2012) [9]) is also a new approach to the conjecture proposed by Montassier et al. (2006) in [27], which says that every planar graph without 4-cycles is acyclically 4-choosable.