论文部分内容阅读
本文考虑的图G是有限,简单(无环,无重边),无向图.如果图G=(V, E)能被嵌入到一个平面使得边仅在端点处相交,称它是可平面的.可平面图在平面内的一个嵌入叫平面图.设G=(V, E)是顶点集为V,边集为E的平面图.图G的一个k-染色是一个映射φ:V→{1,2,...,k}满足任意uv∈E使得φ(u)≠φ(v).若图G存在一个k-染色,则称G是k-可染的. 在定义图G的k-染色φ时,其中集合{1,2,...,k}称为图G每个顶点的可用色集合.若允许可用色集合多样化,我们就得到列表染色的概念.更准确地说,若(V) v∈V,都配置一个列表可用色L(v),则L={L(v)|v∈V}被称为图G的一个染色列表配置.如果(V)v∈V都有|L(v)|=k,则L被称为图G的一个列表配置.若(V)k-列表配置L,都能从L(v)中选择一个颜色v,使得对任意边xy∈E满足φ(x)≠φ(y),则称图G是列表k-可染的,或者称图G是k-可选的.显然对每个v∈V可以选择列表L(v)={1,2,...,k}.因此,若图G是k-可选的,一定是k-可染的.但是,反之则不然. 设d1,d2,...,dk是非负整数,且G=(V,E)是分别以V及E为顶点集和边集的图.图G的一个(d1,d2,...,dk)-染色是一个映射φ:V→{1,2,...,k}使得子图G[Vi]的最大度至多为di,其中Vi={v∈V|φ(vi)=i}.若G有一个(d1,d2,...,dk)-染色,则说G是(d1,d2,...,dk)-可染的.若d1=d2=...=dk=d,则称G是d-非正常k-可染的,或(k,d)*-可染的.若(V)v∈V均配置一个列表可用色L(v),且满足存在一个(L,d)*-可染的,则称图G是(L,d)*-列表可染的,或者称图G是(L,d)*-可选的.易知图G是(L,d)*-可选的,一定是(L,d)*-可染的.但是,反之不成立. 正常列表染色是非正常列表染色的特殊情况,非正常列表染色是正常列表染色的延伸和推广. 1996年,Gutner证明了确定一个平面图是否为3-或4-可选的问题是NP-hard的.所以,证明一个平面图是3-或4-可选的充分条件变得十分有意义.1999年,Eaton等人猜想每个平面图都是(4,1)*-可选的.基于这些猜想和问题,诸多专家和学者对其进行了分析和研究,解决了很多的问题,同时也提出了一些猜想.后人展开了相关的研究并取得了一系列的成果. 本文分为三章,主要围绕猜想及相关问题展开研究,所得结论改进了现有的一些结果.第一章介绍了本论文所涉及的相关定义与符号,并做了一个关于正常列表染色和非正常列表染色的研究现状的综述.第二章介绍不含短圈且限制三角形距离的平面图是3-列表可染的.第三章介绍3,4-圈不邻且不含8-圈的平面图是(3,1)*-列表可染的.