首页 | 本学科首页   官方微博 | 高级检索  
     


Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles
Authors:Haihui Zhang  Baogang Xu
Affiliation:a School of Mathematical Science, Nanjing Normal University, 122, Ninghai Road, Nanjing, 210097, China
b Department of Mathematics, Huaiyin Teachers College, Huaian, Jiangsu, 223300, 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):vV}, there exists a proper acyclic coloring ? of G such that ?(v)∈L(v) for all vV(G). If G is acyclically L-list colorable for any list assignment with |L(v)|≥k for all vV, 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].
Keywords:Acyclically choosability   Planar graph   Cycle
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号