图的无圈非正常列表染色

研究图的无圈非正常列表染色是当前图论领域的热点与难点问题.通过对极小反例G的结构分析,利用色延拓和色置换等方法证明了:最大度为4的非4-正则图是无圈(3,3)^*-可选的.所得结果推广了无圈非正常列表染色的若干结论.

欧拉公式的一个应用

对于图G的所有顶点v∈V(G)的每个满足|L(v)|=m的列表分配L,如果G总存在一个L-染色,使得G的每个顶点至多有d个邻点与它自己染相同的颜色,则称图G是d-缺陷m-可选的。Ko-wei Lih等结合欧拉公式用放电的方法证明了每个不含4-圈和i-圈的平面图是1-缺陷3-可选的,其中i∈|5,6,7|。对于2-连通图,只用欧拉公式就能证明他们的结果。

不含相邻短圈的平面图的 (3, 1)*-可选性

图 G的一个颜色列表配置 L是指给 G中的每个顶点 v都分配一个可用色集 L(v)。 如果在映射 ?下对任意 v ∈ V (G)均满足 ?(v) ∈ L(v),使得在 v的邻点中至多有 d个顶点的颜色为 ?(v),那 么我们称 G是 (L, d)?-可染的。 如果对任意颜色列表配置 L = {L(v)||L(v)| ≥ k, v ∈ V (G)}, G都 是 (L, d)?-可染的,那么我们就称 G 是 (k, d)?-可选的。 Xu 和Zhang 猜想:不含相邻 3-圈的平 面图是 (3, 1)?-可选的。 在本文中,我们将证明不含相邻 k-圈的平面图是 (3, 1)?-可选的,其中k ∈ {3, 4, 5}。

不含相邻单圈的平面图是(3,1)^(*)-可选的

给定图G的一个列表配置L,给每个v∈V(G)分配一个颜色列表L(v).一个(L,d)^(*)-染色是指存在一个可给每个顶点v∈V(G)分配π(v)∈L(v)的映射π,使得v至多只有d个邻点与v染相同的颜色.如果每个v∈V(G)的颜色列表都满足|L(v)|≥k时,图G有一个(L,d)^(*)-染色,那么称G是(k,d)^(*)-可选的.本文证明了每个不含相邻k-圈的平面图是(3,1)^(*)-可选的,其中k∈{3,4,5}.