论文部分内容阅读
本文研究列表染色的若干问题,包括图的色-可选择性和Ohba猜想、某些平面图的(k,l)-可选择性和(k,l)-边-可选择性,以及图(尤其是完全多部图)的唯一列表可染性.
如果图G满足Ch(G)=χ(G),则称G是色-可选择的.关于图的色-可选择性,2002年Ohba[71]给出猜想:如果图G满足|V(G)|≤2χ(G)+1,则G是色-可选择的.容易发现Ohba猜想成立当且仅当其对完全多部图成立,但是对完全多部图Ohba猜想被验证的情况只有图K3*2,2*(k-3),1、K3,2*(k-1)和Kt+3,2*(k-t-1),1*t·本文证明:完全多部图Kt+2,3,2*(k-t-2),1*t(t=2,3,4;k≥t+2)是色-可选择图.因此得到,对图Kt+2,3,2*(k-t-2),1*t(t=1,2,3,4;k≥t+2)及其所有k-色子图Ohba猜想成立.对独立数最大为3的图,2004年Ohba[72]证明了Ohba猜想的一个较弱的形式:如果图G满足|V(G)|≤2χ(G),且G的独立数最大为3,则G是色-可选择的.在此我们证明:若r≤t+1且k≥r+t,则Ch(K3*r,2*(k-r-t),1*t)=χ(K3*r,2*(k-r-t),1*t)=k.此结果表明:在如上Ohba的论断中,条件|V(G)|≤2χ(G)可以换成|V(G)|≤2χ(G)+1.即对每个独立数最大为3的图及其所有χ(G)-色子图Ohba猜想成立.
图的(k,l)-可选择性问题是图的k-可选择性问题的推广.关于图的(k,l)-可选择性,1979年Erdos等人[26]提出了如下猜想:对任意整数m≥1,每一个(k,l)-可选择的图G也是(km,lm)-可选择的.1996年Tuza和Voigt[94]证明了这个猜想在k=2和l=1的情形是正确的,但是对任意的(k,l)验证这个猜想的工作还相差甚远.本文证明:对任意整数m≥1,每一个没有t-圈(t=3,4,5或6)的平面图是(4m,m)-可选择的.这一结果推广了分别由Lam等人[65]、由Wang和Lih[106]、由Fijavz等人[28]给出的如上图都是4-可选择的结果.另一方面,我们还证明:如果一个平面图G不包含t-圈(t=3,4,5或6)且△(G)≠4,则对任意整数m≥1,G是(sm,m)-边-可选择的,这里当t∈{3,4,5},或t=6但△(G)≠5时,s=△(G)+1;当t=6且△(G)=5时,s=7.除了△(G)=4以及t=6且△(G)=5的情况之外,该结果推广了分别由Wang和Lih[105,106]、Zhang和Wu[114]、王维凡[117]给出的不包含t-圈(t=3,4,5或6)的平面图都是(△(G)+1)-边-可选择的结果.此外,作为我们主要结果的推论得到:每一个没有4-圈的平面图G都是(△(G)十1)-边-可选择的.该结果也改进了Zhang和Wu给出的结果:如果图G是没有4-圈的平面图,则G是s-边-可选择的,这里当△(G)≠5时,s=△(G)+1;当△(G)=5时,s=7.
如果图G存在一个k-列表安排L,使得G有唯一的一个L-染色,则称G是唯一k-列表可染的,简称G是UkLC图.1999年Mahdian和Mahmoodian[67]特征化了U2LC图.2001年Ghebleh和Mahmoodian[32]深入地研究了完全多部图的唯一列表可染性,尤其是唯一3-列表可染性,除去9个完全多部图不能确定之外,他们特征化了U3LC完全多部图.与此同时,针对这9个被剔除的图,他们提出了如下开放问题:查证图K2,2,r,r=4,5,…,8,K2,3,4,K1*4,4,K1*4,5和K1*5,4不是U3LC图.2004年Zhao等人[115]证明了图K2,3,4不是U3LC图.本文首先研究U2LC图特征化定理证明的简化问题.然后证明:图K2,2,r,r=4,5,…,8,K1*4,4,K1*4,5和K1*5,4都不是U3LC图.因此,唯一3-列表可染的完全多部图得到全面特征化.