Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles
Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles
复制标题
DOI：
10.1016/j.disc.2009.05.018
复制
发表时间：
2009-10
期刊：
影响因子：
--
通讯作者：
Haihui Zhang;Baogang Xu
中科院分区：
文献类型：
--
作者：
Haihui Zhang;Baogang Xu
如果图G=(V，E)不含双色圈，则G=(V，E)的真点染色是无圈的。一个图G是圈L列表可染的，如果对给定的列表分配L={L(V)：v∈V}，存在G的一个真正的无圈着色ϕ，使得ϕ(V)∈L(V)对所有v∈V(G).如果G对任意列表赋值|L(V)|≥k对所有v∈V都是圈L列表可染的，则G是圈k可选的。本文证明了既无4圈又无弦6圈的平面图是无圈5-可选的。这推广了[M.Montassier，A.Raspaud，W.Wang，Acycle 5-Choosable of Plane Groups Without Small Cycle，J.Graph the54(2007)245-260]的结果，以及[M.Montassier，P.Ochem，A.Raspaud，on the Acycle Choosable of Ggraph，J.Graph The51(4)(2006)281-300]的一个推论。
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(G). 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 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].