Acyclic 6-choosability of planar graphs without adjacent short cycles
Acyclic 6-choosability of planar graphs without adjacent short cycles作者机构:Department of MathematicsZhejiang Normal University
出 版 物:《Science China Mathematics》 (中国科学:数学(英文版))
年 卷 期:2014年第57卷第1期
页 面:197-209页
核心收录:
学科分类:07[理学] 070104[理学-应用数学] 0701[理学-数学]
基 金: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
主 题:acyclic coloring,acyclic choosability,planar graph
摘 要:A proper vertex coloring of a graph G is acyclic if G contains no bicolored *** 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∈*** G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically *** 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).