平面图的正常列表染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:lavina0526
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文考虑的图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-可染的.反之则不然.  Erd(o)s et al.[1]刻画了所有的2-可选图;Thomassen[2]证明了可平面图的5-可选性;Voigt[3]证明了存在一个非4-可选的平面图;Gutner[4]证明确定一个平面图是否为3-或4-可选的问题是NP-hard的.所以,证明一个平面图是3-或4-可选的充分条件变得十分有意义.基于这些猜想和问题,诸多学者对上述问题展开研究并取得了一系列的成果.  本文分三章展开,主要围绕猜想及相关问题展开研究,所得结论改进了现有的一些结果.第一章介绍了本论文所涉及的相关定义与符号,并做了一个关于正常列表染色研究现状的综述;第二章介绍不含三角4-圈的平面图是4-可选的;第三章介绍不含短圈且限制三角形距离的平面图是3-可选的.
其他文献
随着理论研究的不断深入和工程应用的迫切需要,生活中大量的现实问题都被刻画成非线性系统模型,其中较为常见的两类系统是耦合系统和时滞系统.更为复杂的是,有的问题既需要考虑
以株型好、柱头无色的培矮64S选系17S为母本,以保持系201B为父本杂交,经5 a定向选育,育成水稻温敏核不育系33S。该不育系不育起点温度低(
在这篇文章中,我们主要研究索赔时间间隔服从Erlang(2)分布的SparreAndersen风险模型下,破产时与破产时总索赔数量的联合分布。首先定义了带有索赔次数的期望折现罚金函数,运用
本文分为三章,主要研究了乘积Laguerre超群上的广义小波和Weyl变换及其对于余弦合成信号的特征提取与其阈值去噪。  第一章借助于小波变换定义了乘积Laguerre超群上的广义小
约束矩阵方程问题是指在满足约束条件下的矩阵集合中求解矩阵方程的问题.该问题广泛应用于结构设计、生物学、分子光谱学、振动理论、有限元等领域,已成为数值代数领域中最热
请下载后查看,本文暂不支持在线获取查看简介。 Please download to view, this article does not support online access to view profile.
目前,我国已基本形成国有企业、股份制企业、外商投资企业、个体私营企业等多种经济成份相互竞争、互为作用、共同发展的局面,极大地加快了建设有中国特色社会主义的步伐,成
分枝过程是一种用来描述物种的繁衍过程的数学模型,该模型在种群繁衍、粒子裂变、流行病传播等领域均有着的应用.确定环境分枝过程主要研究粒子的灭绝、爆炸、收敛等问题,但
本文研究了两类分数阶p-Laplacian方程弱解的存在性,分别在次临界与临界的情形下建立了方程弱解的存在性定理.  类型一:考虑了次临界情形的分数阶p-Laplacian方程(-△)spu+V