A note on list improper coloring of plane graphs
A note on list improper coloring of plane graphs
复制标题
关于平面图着色不当的列表的注释
DOI：
10.1016/j.dam.2008.06.023
复制
发表时间：
2009-01
影响因子：
1.1
通讯作者：
许宝刚
中科院分区：
文献类型：
--
作者：
董伟;许宝刚
G的顶点的列表赋值L是指对任意v∈V（G），颜色集合L（v）到顶点v的赋值。一个（L，d）-着色是一个映射<$N，它给每个顶点v∈V（G）分配一个颜色<$N（v）∈L（v），使得v的最多d个邻居接收颜色<$N（v）。一个图称为（k，d）可选图，如果G对每个列表分配L都允许（L，d）可选染色，且|L（v）|对所有v∈V（G）≥k.本文证明了：对于任意l∈{8，9}，不含4-圈和l-圈的平面图都是（3，1）-可选的.
A list-assignment L to the vertices of G is an assignment of a set L(v) of colors to vertex v for every v∈V(G). An (L,d)∗-coloring is a mapping ϕ that assigns a color ϕ(v)∈L(v) to each vertex v∈V(G) such that at most d neighbors of v receive color ϕ(v). A graph is called (k,d)∗-choosable, if G admits an (L,d)∗-coloring for every list assignment L with |L(v)|≥k for all v∈V(G). In this note, it is proved that every plane graph, which contains no 4-cycles and l-cycles for some l∈{8,9}, is (3,1)∗-choosable.
登录
查看更多内容
DOI：
10.1017/cbo9780511721328
发表时间：
2001
期刊：
--
影响因子：
--
作者：
J. Hirschfeld
通讯作者：
J. Hirschfeld
DOI：
10.1057/jors.1977.45
发表时间：
1978-03
期刊：
--
影响因子：
--
作者：
E. Lloyd;J. Bondy;U. Murty
通讯作者：
E. Lloyd;J. Bondy;U. Murty
DOI：
10.1017/s0963548399003752
发表时间：
1999-05
期刊：
Combinatorics, Probability and Computing
影响因子：
--
作者：
R. Škrekovski
通讯作者：
R. Škrekovski
DOI：
--
发表时间：
1997
期刊：
--
影响因子：
--
作者：
N. Eaton;Thomas C. Hull
通讯作者：
N. Eaton;Thomas C. Hull
DOI：
10.1002/9781118600207.ch10
发表时间：
2013-02
期刊：
--
影响因子：
--
作者：
D. de Werra;D. Kobler
通讯作者：
D. de Werra;D. Kobler