平面图的无圈点列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:tiger20091
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图G的一个正常顶点染色是指映射φ(:)V(G)→{1,2,…,k},使得任意两个相邻的点染有不同颜色.若G有一个正常k-点染色,那么就称图G是k-点可染的.图G的色数是指G有一个正常k-顶点染色的数k的最小值,用x(G)表示.  假若染色π是图G的正常顶点染色,并且对于G中任何两种颜色所导出的子图均不构成圈,那么我们称染色π是G的一个无圈染色.图G的无圈色数是指G有一个无圈k-顶点染色的数k的最小值,用xa(G)表示.若G有一个正常的无圈染色π,使得对每一个顶点v∈V,都有π(v)∈L(v),则称G是无圈L-可染的或者称π是G的一个无圈L-染色.若对满足|L(v)|≥k,v∈V的色列表L都是无圈L-可染的,那么称G是无圈k-点列表可染的或k-可选的.图G的无圈列表色数或者无圈选择数是指G是无圈k-点列表可染的数k的最小值,用xla(G)表示.  2002年,Borodin,Fon-Der Flass,Kostochka,Raspaud和Sopena证明了每个平面图是无圈7-点列表可染的,并提出了极具挑战性的猜想,即:每个平面图是无圈5-点列表可染的.此猜想目前仍未被完全解决.因此,围绕这个猜想,Montassier,Raspaud和Wang提出了另外一个猜想:每个不包含4-圈的平面图是无圈4-点列表可染的.但遗憾的是,此猜想也未完全证明.  本学位论文主要围绕以上两个猜想,着重研究了平面图的无圈点列表染色问题.本文共分三章:  在第一章中,我们介绍了本文所涉及的有关概念,并简述了无圈点列表染色的研究现状.  在第二章中,我们证明了:不含相邻的4-圈和i-圈的平面图是无圈6-点列表可染的,其中i∈{3,4,5,6}.  在第三章中,我们证明了以下两个结果:  (1)不含4-圈,相邻5-圈,相邻的3-圈和6-圈的平面图是无圈4-点列表可染的.  (2)若平面图G中的i-圈和j-圈的距离至少为1,其中3≤i,j≤5,则G是无圈4-点列表可染的.
其他文献
直觉模糊集作为模糊集的推广,它引入了真隶属度和假隶属度的概念,可以更广泛的解释事物或现象的不确定性.并且与模糊推理研究方法类似,直觉模糊推理的核心问题是求解直觉模糊
不动点理论在非线性微分方程、偏微分方程、经济均衡理论及对策理论等许多领域有广泛的应用。但是不动点的存在条件很强,例如,当映射的定义域非紧或映射不连续时,则映射的不动点
本文运用可靠性理论分析研究两类CB级ATSE的可靠性,从而得出双电操CB级ATSE的可靠性高于单电操CB级ATSE可靠性.
随着科学技术的发展,各种各样的图像显示设备层出不穷,既有高分辨率的电脑,也有低分辨率的手机等。如果把同一幅图片放在这些不同设备上显示时,就需要改变图像的尺寸与长宽比例来
本文中所讨论的稀疏模型修正问题是根据实验获得的数据,在系数矩阵稀疏、对称、半正定的约束条件下,对理论建立的二次模型进行修正,使得修正后的模型具有理论模型的结构并且与实
群表示理论是近代数学中发展迅速而且相当活跃的数学分支,它包括群的常表示理论,模表示理论与整表示理论,其中,有限群的常表示理论创立最早,迄今已有一百多年的历史,发展也最完善,是
摘 要:我国是一个水资源十分匮乏的国家,近年来随着我国经济的快速增长,因供水紧张而制约工农业快速发展的矛盾十分突出。火力发电厂在生产过程中要消耗大量的水,每个环节都要排放大量的废水。由于水电所排放的废水对环境的影响越来越严重,如何合理的利用水资源,做到既有利于发展生产、降低运营成本、又能最大限度的保护环境、体现出可持续发展的战略,是热电厂生存和发展的根本。  关键字:废水 环境保护 处理 回用  
拓扑空间和连续映射的同伦分类是代数拓扑学中的重要内容。首先研究以对轮图为缩影的图式流形的同胚分类以及分类数。对轮图以一个顶点为中心,n-1个顶点依次相连围成一个圈,每
本篇论文主要研究内容:  第一章对相关的理论背景和不动点的发展概况进行了概述,说明了研究的内容和意义并给出了一些基本概念和定理.  第二章在2003年,Nakajo与Takahashi