关于图的可选择性与唯一列表可染图研究

摘要

本文研究列表染色的若干问题，包括图的色-可选择性和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-列表可染的完全多部图得到全面特征化.

目录

文摘

英文文摘

论文说明：插图目录

报送博士学位论文简况表及报送博士学位论文简况表（英文）

第一章引言

第二章图的色-可选择性与Ohba猜想

§2.1关于图是色-可选择的若干猜想

§2.2 Ohba猜想的等价形式及其被验证的图类

§2.3对图Kt+2，3，2*(k-t-2)，1*t(t=2，3，4)Ohba猜想成立

§2.4对独立数最大为3的图Ohba猜想成立

第三章某些平面图的(k，l)-(边-)可选择性

第四章完全多部图的唯一列表染色

§4.1关于唯一列表可染图的特征化和一个开放问题

§4.2 U2LC图特征化定理证明的简化

§4.3 U3LC完全多部图Kr,s,t和K1*r,s的若干性质

§4.4关于Ghebleh和Mahmoodian开放问题的研究

参考文献

索引

攻读博士学位期间撰写的学术论文

致谢