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


Acyclic 5-choosability of planar graphs without 4-cycles
Authors:Min Chen
Institution: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):vV}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all vV. 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 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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