平面图的列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:xzjwl
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文考虑的图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)*-列表可染的.
其他文献
图像修复一直以来都是图像处理领域一个很受关注的问题,而且也是进一步图像处理应用的预处理过程.主要是利用一定的算法针对产生划痕和有缺损的图像进行修复,或者从图像中去除
本文主要研究了基于分数布朗运动的Wick型积分的随机微分方程解的存在唯一性和P阶矩估计。   2000年,T.E.Duncan等人(见[62])给出了分数布朗运动Wick型积分的It(o)公式,本文在此
本文研究对象限于简单有限图,对于图G的一个正常顶点k-染色,指的是从G的顶点集合V(G)到颜色集合{1,2,…,k}的一个映射c.使得距离为1的点染的颜色也不同,我们用x(G)来表示满足上述要
近年来,在自然界和社会生活中,众多复杂网络所表现出的小世界特性和无标度特性引起了科学界对复杂网络的研究热潮,这使得复杂网络成为近年来研究的一个热点.本文旨在利用复杂网
本文研究的主要内容是非自治三分量可逆Gray-Scott系统的拉回指数吸引子和一致指数吸引子的存在性.本文主要分为五章:  第一章,首先介绍无穷维动力系统(主要是非自治)的研究现