Acyclic 4-choosability of planar graphs
Acyclic 4-choosability of planar graphs
复制标题
平面图的非循环 4-可选择性
DOI：
10.1016/j.disc.2010.10.003
复制
发表时间：
2011
影响因子：
0.8
通讯作者：
朱绪鼎
中科院分区：
文献类型：
--
作者：
陈敏;Raspaud André;Roussel Nicolas,;朱绪鼎
如果图G=(V，E)不含双色圈，则G=(V，E)的真点染色是无圈的。给定G的一个表赋值L={L(V)|v∈V}，如果存在G的一个真的无圈着色π使得π(V)∈L(V)对所有v∈V都是闭L表可染的，则称G是无圈L-表可染的，如果对任何满足|L(V)|≥k对所有v∈V的表赋值G是闭L表可染的，则G是闭k可选的.本文证明了没有4、7、8圈的平面图是非圈4可选的。
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 π 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 planar graphs without 4, 7, and 8-cycles are acyclically 4-choosable.
登录
查看更多内容
影响因子：
1
作者：
B. Grünbaum
通讯作者：
B. Grünbaum
DOI：
10.1016/j.disc.2007.11.076
发表时间：
2008-12
期刊：
Discret. Math.
影响因子：
--
作者：
Min Chen;Weifan Wang
通讯作者：
Min Chen;Weifan Wang
影响因子：
0.9
作者：
O. Borodin;D. Fon-Der-Flaass;A. Kostochka;A. Raspaud;É. Sopena
通讯作者：
O. Borodin;D. Fon-Der-Flaass;A. Kostochka;A. Raspaud;É. Sopena
DOI：
10.1016/j.disc.2009.05.018
发表时间：
2009-10
期刊：
Discret. Math.
影响因子：
--
作者：
Haihui Zhang;Baogang Xu
通讯作者：
Haihui Zhang;Baogang Xu
影响因子：
--
作者：
O. Borodin
通讯作者：
O. Borodin