平面图的非正常染色

来源 :浙江师范大学 | 被引量 : 0次 | 上传用户:zongduzhicai
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
本文研究的图是有限,简单,无向图.设G=(V,E)是一个图,k是一个正整数.若存在一个映射φ:V→{1,2,…,k}满足:对任意xy∈E,都有φ(x)≠φ(y),则称φ是G的一个k-染色,此时我们称G是k-可染的.给G的每个顶点v分配一个颜色集合L(v),则称L={L(v)|v∈V}是G的一个色列表.若对任意的点v∈V,都能从其相应的色列表L(v)中选取一个颜色φ(v)染给v,使得(V)uv∈E(G),有φ(u)≠φ(v),则称G是L-可染的.若G对任意一个满足|L(v)|≥k的色列表L,G都是L-可染的,则称G是k-列表可染的,也称G是k-可选择的.  设di,i∈{1,2,…,k}是k个非负整数.若能用1,2,…,k这k种颜色对图G=(V, E)的点进行染色,使得染颜色i的点组成的点导出子图G[Vi]的最大度至多为di,i∈{1,2,…,k},则称G是非正常(d1,d2,…,dk)-可染的,或简称(d1,d2,…,dk)-可染的.若d1=d2=…=dk=d,则称G是d-非正常k-可染的,或称(k,d)*-可染的.设d是一个非负整数,L是G的一个色列表.若对每一个L={L(v)|v∈V|L(v)|≥k},我们都能用L(v)中的一种颜色去染v,使得染颜色i的点组成的点导出子图G[Vi]的最大度至多为d,则称G是非正常(k,d)*-可选的,或简称(k,d)*-可选的.  易知,正常染色是非正常染色的特例,非正常染色是正常染色的推广.  1976年,Steinberg提出了一个猜想:既不含4-圈又不含5-圈的可平面图是3-可染的.由于解决著名的Steinberg猜想有很大的难度,Erd(o)s提出这样的一个问题:寻找一个常数C,使得不含4到C-圈的可平面图是3-可染的.  本论文分为四章,主要围绕以上猜想和问题展开研究,所得结论改进了现有的一些结果.第一章介绍了本论文所涉及的有关定义,并对正常染色和非正常染色的研究现状做了一个综述.第二章主要讨论既不含4-圈又不含5-圈的可平面图的非正常染色,第三章主要讨论既不含4-圈又不含6-圈的可平面图的非正常染色.第四章主要讨论不舍4-圈的可平面图的非正常列表染色.
其他文献
2000年Branciari在度量空间的基础上,用四角不等式代替三角不等式提出了矩度量空间的概念,并证明了Banach压缩映象的不动点定理.随后,许多学者将矩度量空间推广为偏矩度量、锥矩
用G=(V,E,F)表示一个以V为顶点集,E为边集,F为面集的平面图.著名的四色定理告诉我们:每个平面图是4色可染的,之后人们的研究兴趣自然转移到平面图的3-染色问题上来.早在1959年,Gr(
学位
学位
企业文化是企业生存和发展的灵魂,也是企业核心竞争力的重要体现。优秀的企业文化既是企业持续、稳定发展的助推器,也是企业凝聚力和生命力的源泉。2005年,金牛能源集团成立,经过几年的探索和发展,企业文化建设取得了可喜的成绩,提炼出了“民航精神”,并逐步形成了一些具有鲜明特色的企业文化。然而,从实际情况看,煤炭行业文化特别是煤炭企业文化建设的路还很漫长,部分基层企业在文化建设过程中还存在着“四轻四重”等
众所周知,Hamilton系统是用来描述天体运动的轨道的,而寻找一般的Hamilton系统所具有的各种不变量用以研究该系统的解,已成为人们关心的问题之一.本文利用临界点理论,证明了如下
摘 要:井下作业现场是石油开采的重要手段。在石油井下作业中,如果不注意安全管理,不及时消除人为、机械等原因造成的安全因素,抱着侥幸的心理强行作业,不仅对现场工作人员和其他人员造成人身伤害,而且还会给企业造成严重的经济和产量损失。本文就加强油田井下作业现场安全管理进行探讨。  关键词:井下作业 现场 安全 管理  随着原油价格的持续飞涨和经济发展对人们思想的冲击,很多商家受经济利益的驱使诱惑,为谋取
学位
最优化方法在我们的日常生活中的应用非常广泛。共轭梯度方法是解决大规模无约束优化问题中一种比较重要的方法。本文提出了两种混合的带参数的共轭梯度算法。对这两种算法给