Premium
Planar graphs without 4‐cycles are acyclically 6‐choosable
Author(s) -
Wang Weifan,
Chen Min
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20381
Subject(s) - combinatorics , planar graph , mathematics , vertex (graph theory) , graph , list coloring , discrete mathematics , graph power , line graph
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