2006/11/16 by Mickaël Montassier, André Raspaud, Weifan Wang
paper · doi:10.1002/jgt.20206
Abstract A proper vertex coloring of a graph G = ( V,E ) is acyclic if G contains no bicolored cycle. A graph G is acyclically L ‐list colorable if for a given list assignment L = L ( v ): v : ∈ V , there exists a proper acyclic coloring ϕ of G such that ϕ( v ) ∈ L ( v ) for all v ∈ V . If G is acyclically L ‐list colorable for any list assignment with | L ( v )|≥ k for all v ∈ V , then G is acyclically k ‐choosable. In this article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007