平面图的非正常2-染色的研究

论文摘要

图论是一门发展非常迅速的科学,从它的出现到理论体系的完整建构不过几百年的时间,但它的应用领域却极其广泛,例如物理学,运筹学,计算机科学,控制论,信息论及经济管理等学科都需要图理论来构建数学应用模型.而图染色问题是图理论的主要研究领域之一.它起源于著名的“四色定理”,即给平面上的任何一张地图染色,使得有公共边界的国家所染颜色不同且最多使用四种颜色.本文研究的图是有限,简单,无向图.设G=（V,E）是一个图,k是一个正整数.若存在一个映射φ:V → {1,2,...,k}满足:对任意x∈ E,都有φ（x）≠φ（y）,则称φ是G的一个k-染色,我们称G是k-可染的.这种染色我们称之为图G的正常染色.设d1,d2,...,dk是k个非负整数,若图G=（V,E）的顶点集V能被剖分成k个子集V1,V2,...,Vk,使得对任意的i=1,2,...,k,Vi的点导出子图G[Vi]的最大度至多为di,则称图G是非正常（d1,d2,...,dk）-可染的,或简称为（d1,d2,...,dk）-可染的.若d1=d2=...=dk=d,则称G是d-非正常k-可染的.对一个平面图G,用F（G）表示面集.若两个面至少有一条公共边时,我们称这两个面是相邻的.由上面定义可以看出,正常染色是非正常染色的特例,非正常染色是正常染色的推广.用这个概念,著名的四色定理可叙述为:每个平面图是（0,0,0,0）-可染的[10,11].对于一个（d1,d2,d3）-可染的平面图,1976年,Steinberg提出猜想:每个不含4-圈和5-圈的可平面图是（0,0,0）-可染的.虽然这个猜想已经被证明是不成立的,但在这一猜想的推动下,仍然得到了许多著名的结果,例如,每个不含4-圈和5-圈的平面图是（2,1,0）-可染的[6]（3,0,0）-可染的[19]等等.对于一个（d1,d2）-可染的平面图,同样通过限制围长和禁掉某些特殊圈的方法,得到了很多有名的结果,例如,g（G）≥ 6的平面图是（2,2）-可染的[4],Pongpat,Kittikorn[25]在2017年用权转移的方法证明了不含4-圈和5-圈的平面图为（3,5）,（4,4）,（2,9）-可染的等.基于上述对平面图的非正常2-可染的研究,我们主要讨论不含4-圈和禁掉部分特殊圈的平面图的非正常点染色问题.论文分为四章,第一章介绍了一些基本概念和符号以及平面图的非正常染色的历史与现状.然后我们将利用权转移的方法在第二章、第三章和第四章中分别证明了:定理1.4.1.不含4-圈和无3-圈和5-圈、6-圈相邻,无相邻5-圈的平面图是（3,7）-可染的.定理1.4.2.不含4-圈和2度点不在3圈上,无相邻5-圈,无相邻5-圈和6-圈的平面图是（3,7）-可染的.定理1.4.3.不含4-圈和2度点不在3圈上,无共点5-圈的平面图是（2,9）-可染的.

论文目录

• 中文摘要
• 英文摘要
• 第一章 引言
•   §1.1 基本术语与符号
•   §1.2 图的染色问题的历史与发展
•   §1.3 平面图的非正常2-染色问题的研究现状与主要成果
•   §1.4 本文主要结果
• 第二章 定理1.4.1的证明
•   §2.1 结构分析
•   §2.2 权转移
• 第三章 定理1.4.2的证明
•   §3.1 结构分析
•   §3.2 权转移
• 第四章 定理1.4.3的证明
•   §4.1 结构分析
•   §4.2 权转移
• 参考文献
• 在学期间发表的学术论文
• 致谢

文章来源

类型: 硕士论文

作者: 周倩倩

导师: 孙磊

关键词: 非正常染色,平面图,权转移

来源: 山东师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 山东师范大学

分类号: O157.5

DOI: 10.27280/d.cnki.gsdsu.2019.000005

总页数: 50

文件大小: 2359K

下载量: 10