平面图的DP染色和松驰染色问题研究

论文摘要

四色猜想,又称四色问题,是世界三大数学猜想之一。四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”也就是说在不引起混淆的情况下一张地图只需四种颜色来标记就行。用数学语言表示即“将平面任意地细分为不相重叠的区域,每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。很多人虽然证明了二维平面内无法构造五个或五个以上两两相邻区域,但却没有将其上升到逻辑关系和二维固有属性的层面,以致出现了很多伪反例。不过这些恰恰是对图论严密性的考证和发展推动。1976年6月,在美国伊利诺斯大学的两台不同的电子计算机上,用了1200个小时,作了100亿个判断,结果没有一张地图是需要五色的,最终证明了四色定理,轰动了世界。但是计算机的证明,只是依靠数量庞大的计算,不符合数学严密的逻辑体系,故而至今仍有无数专家学者投身其中研究,想要寻求四色定理的严谨数学证明。所以,图的染色问题一直是图论研究的一个中心问题也是热点问题。图的染色理论有很多分支,如边染色、点染色、面染色和全染色等。其中研究最多,结果也较完善的就是图的点染色。本文主要研究图的两种点染色问题:DP染色和松弛染色。本文主要由四个章节组成,主要内容如下:在第一章,我们首先给出了本文用到的基本概念和记号,接着介绍了图的DP染色和松弛染色的研究背景和研究现状。在第二章,我们着重研究平面图的DP染色问题。证明了以下两个结果:·其一,如果一个平面图G不包含长度为4或者5的圈,同时三角形之间距离不小于3,或者图G不包含长度为4到6的圈同时三角形之间的距离不小于2,那么这个平面图G是DP-3-可着色的,显然也是3-可选择的,改进了Montassier,Raspaud和Wang[33]的结果。由于存在不含长度为4或者5的圈且三角形之间距离不小于1却不能3-可选择的图,所以这个结果也是相当强的。·其二,如果一个平面图G不包含长度为{5,6,7}的圈且三角形之间的距离至少为2,那么这个平面图G是DP-3-可染的。这个结果改进了Li,Chen和Wang[29]在2016年的结果。在第三章,我们着重研究平面图的松弛染色问题,并且证明了不含5-圈和K4-且不含相邻4-圈的平面图是（2,0,0）-可着色的。改进了Chen,Wang,Liu和Xu[16]的结果和Liu,Li和Yu[30]的结果。因为Steinberg猜想已经被证伪,所以这是一个很强的结论。第四章作为本文的结束部分,我们提出了可以进一步考虑的研究问题。

论文目录

摘要

Abstract

第一章绪论

1.1 基本概念和符号

1.2 研究背景

1.3 图的几类常见染色

1.3.1 图的列表染色

1.3.2 图的DP染色

1.3.3 图的松弛染色

1.4 本文的主要结果

第二章平面图的DP染色

2.1 预备知识

2.2 工具引理的简单应用

2.2.1 定理2.1.1的证明

2.3 工具引理的更进一步应用

2.3.1 定理2.1.3的证明

2.3.2 定理2.1.4的证明

第三章平面图的松弛染色

3.1 预备知识

3.2 定理3.2.1的证明

第四章归纳展望

参考文献

攻读博士学位期间完成的论文

致谢

文章来源

类型: 博士论文

作者: 殷瑜雪

导师: 李相文

关键词: 四色定理,染色,松弛染色,平面图

来源: 华中师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 华中师范大学

分类号: O157.5

总页数: 89

文件大小: 3634K

下载量: 43

平面图的DP染色和松驰染色问题研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢