Acyclic 5-choosability of planar graphs without 4-cycles
Acyclic 5-choosability of planar graphs without 4-cycles
复制标题
DOI：
10.1016/j.disc.2007.11.076
复制
发表时间：
2008-12
期刊：
影响因子：
--
通讯作者：
Min Chen;Weifan Wang
中科院分区：
文献类型：
--
作者：
Min Chen;Weifan Wang
图G=（V，E）的正常点染色是无圈的，如果G不含双色圈.一个图G是无圈L-列表可着色的，如果对给定的列表分配L={L（v）：v∈V}，存在G的一个正常无圈着色π，使得对任意v∈V，π（v）∈L（v）.如果G对任意列表赋值是非循环L-列表可着色的，|L（v）|≥k，则G是无圈k-可选的.本文证明了每个不含4-圈和距离小于3的不含两个3-圈的平面图是无圈5-可选的。这改进了[M. Montassier，P. Ochem，A. Raspaud，On the acyclic choosability of graphs，J. Graph Theory 51（2006）281-300]，其中指出围长至少为5的平面图是非循环5-choosable的。
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∈V}, there exists a proper acyclic coloring π of G such that π(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 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.