Acyclic 4-choosability of Planar Graphs with Girth at Least 5
Mickaël Montassier · Birkhäuser Basel eBooks · 2006
A proper vertex coloring of a graph G = ( V,E ) is acyclic if G contains no bicolored cycle. A graph G is L -list colorable, for a given list assignment L = L ( v ): v ∈ V , if there exists a proper coloring c of G such that c ( v ) ∈ L ( v ) for all v ∈ V . If G is L -list colorable for every list assignment with | L ( v )| ≥ κ for all v ∈ V , then G is called κ -choosable. A graph is said to be acyclically κ -choosable if these L -list colorings can be chosen to be acyclic. In this paper, we prove that if G is planar with girth g ≥ 5, then G is acyclically 4-choosable. This improves the result of Borodin, Kostochka and Woodall [ [BKW99] ] concerning the acyclic chromatic number of planar graphs with girth at least 5. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.