科研之友
微信
新浪微博
Facebook
分享链接
摘要
A proper vertex coloring of a graph G = (V, E) is acyclic if G contains no bicolored cycle. Given a list assignment L = {L(v)|v?V} of G, we say G is acyclically L-list colorable if there exists a proper acyclic coloring p of G such that p(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 article we prove that every planar graph without 4-cycles and without intersecting triangles is acyclically 5-choosable. This improves the result in [M. Chen and W. Wang, Discrete Math 308 (2008), 62166225], which says that every planar graph without 4-cycles and without two triangles at distance less than 3 is acyclically 5-choosable.
- 出版日期2012-6
- 单位浙江师范大学
