Acyclic 5-choosability of planar graphs without 4-cycles |
| |
Authors: | Min Chen |
| |
Affiliation: | Department of Mathematics, Zhejiang Normal University, 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 without 4-cycles and without two 3-cycles at distance less than 3 is acyclically 5-choosable. This improves a result in [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (2006) 281-300], which says that planar graphs of girth at least 5 are acyclically 5-choosable. |
| |
Keywords: | Planar graphs Acyclic coloring Choosable Cycle |
本文献已被 ScienceDirect 等数据库收录! |
|