摘要
A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).
A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L（v）｜v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ（v）∈L（v）for all v∈V.If G is acyclically L-colorable for any list assignment L with｜L（v）｜k for all v∈V（G）,then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen（2009）.
基金
supported by National Natural Science Foundation of China (Grant Nos. 11071223 and 11101377)
Natural Science Foundation of Zhejiang Province,China (Gran No. Z6090150)
Zhejiang Innovation Project (Grant No. T200905)
Zhejiang Normal University Innovation Team Program
