Article ID Journal Published Year Pages File Type
4648996 Discrete Mathematics 2010 6 Pages PDF
Abstract

Let G=(V,E)G=(V,E) be a graph. A proper vertex coloring of GG is acyclic if GG contains no bicolored cycle. Namely, every cycle of GG must be colored with at least three colors. GG is acyclicallyLL-list colorable if for a given list assignment L={L(v):v∈V}L={L(v):v∈V}, there exists a proper acyclic coloring ππ of GG such that π(v)∈L(v)π(v)∈L(v) for all v∈Vv∈V. If GG is acyclically LL-list colorable for any list assignment with |L(v)|≥k|L(v)|≥k for all v∈Vv∈V, then GG is acyclically kk-choosable.In this paper, we prove that planar graphs with neither {4,5}{4,5}-cycles nor 8-cycles having a triangular chord are acyclically 4-choosable. This implies that planar graphs either without {4,5,7}{4,5,7}-cycles or without {4,5,8}{4,5,8}-cycles are acyclically 4-choosable.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,