Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles

作者：Zhang Haihui^*; Xu Baogang

来源：Discrete Mathematics, 2009, 309(20): 6087-6091.

DOI：10.1016/j.disc.2009.05.018

• Acyclically choosability
• Planar graph
• 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 epsilon V}, there exists a proper acyclic coloring phi of G Such that phi(v) epsilon L(v) for all v epsilon V(G). If G is acyclically L-list colorable for any list assignment with |L(v)| >= k for all v epsilon V, then G is acyclically k-choosable. In this paper it is proved that every planar graph with neither 4-cycles nor chordal 6-cycles is acyclically 5-choosable. This generalizes the results of [M. Montassier. A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory 54 (2007) 245-260]. and a corollary of [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs,J. Graph Theory 51 (4) (2006) 281-300].

• 出版日期2009-10-28
• 单位南京师范大学; 南宁师范大学