Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419551 | Discrete Applied Mathematics | 2010 | 7 Pages |
An acyclic coloring of a graph GG is a coloring of its vertices such that: (i) no two adjacent vertices in GG receive the same color and (ii) no bicolored cycles exist in GG. A list assignment of GG is a function LL that assigns to each vertex v∈V(G)v∈V(G) a list L(v)L(v) of available colors. Let GG be a graph and LL be a list assignment of GG. The graph GG is acyclically LL-list colorable if there exists an acyclic coloring ϕϕ of GG such that ϕ(v)∈L(v)ϕ(v)∈L(v) for all v∈V(G)v∈V(G). If GG is acyclically LL-list colorable for any list assignment LL with |L(v)|≥k|L(v)|≥k for all v∈V(G)v∈V(G), then GG is said to be acyclically kk-choosable. Borodin et al. proved that every planar graph with girth at least 7 is acyclically 3-choosable (Borodin et al., submitted for publication [4]). More recently, Borodin and Ivanova showed that every planar graph without cycles of length 4 to 11 is acyclically 3-choosable (Borodin and Ivanova, submitted for publication [7]). In this note, we connect these two results by a sequence of intermediate sufficient conditions that involve the minimum distance between 3-cycles: we prove that every planar graph with neither cycles of lengths 4 to 7 (resp. to 8, to 9, to 10) nor triangles at distance less than 7 (resp. 5, 3, 2) is acyclically 3-choosable.