2009/04/06 by Weifan Wang, Min Chen · 1 citation
Computer Science · #Advanced Graph Theory Research
paper · doi:10.1002/jgt.20381
openalex publication_date 2009/04/06 · 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. 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 paper we prove that every planar graph G without 4‐cycles is acyclically 6‐choosable. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 307–323, 2009