2011/04/14 by Min Chen, André Raspaud · 2 citations
Computer Science · #Advanced Graph Theory Research
paper · doi:10.1002/jgt.20604
openalex publication_date 2011/04/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Abstract A proper vertex coloring of a graph G = ( V, E ) is acyclic if G contains no bicolored cycle. Given a list assignment L = L ( v )| v ∈ V of G , we say G is acyclically L ‐list colorable if 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 without 4‐cycles and without intersecting triangles is acyclically 5‐choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 6216–6225], which says that every planar graph without 4‐cycles and without two triangles at distance less than 3 is acyclically 5‐choosable. © 2011 Wiley Periodicals, Inc. J Graph Theory