Planar graphs without 4‐cycles are acyclically 6‐choosable |
| |
Authors: | Weifan Wang Min Chen |
| |
Institution: | Department of Mathematics, Zhejiang Normal University, Zhejiang Jinhua 321004, China |
| |
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 |
| |
Keywords: | acyclic coloring choosability planar graph cycle |
|
|