Acyclic 5-choosability of planar graphs without 4-cycles

作者：Chen Min; Wang Weifan

来源：Discrete Mathematics, 2008, 308(24): 6216-6225.

DOI：10.1016/j.disc.2007.11.076

• Planar graphs
• Acyclic coloring
• Choosable
• Cycle

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 is an element of V}, there exists a proper acylic coloring pi of G such that pi(v) is an element of L(v) for all v is an element of 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.

• 出版日期2008-12-28
• 单位浙江师范大学