图的无圈全染色

论文摘要

图的染色理论是在“四色定理”的基础上发展起来的.Coleman等人以无圈染色为模型,结合代入法计算了Hessian矩阵,使得更多人开始关注无圈染色.本文研究的图都是无向有限的非空图.我们用G=（V,E）来表示一个图,这里V=V（G）和E=E（G）分别用来表示图G的顶点集和边集.用△（G）,δ（G）分别表示图G的最大度和最小度.图G中最短圈的长度称为图G的围长,记作g（G）.平面图是指一个图可以画在平面上并且它的任意两条边在端点外不会相交.图G的正常的k-全染色是指从图G的顶点集和边集到颜色集[k]的一个映射,使得任意两个相邻或者相关联的元素x,y ∈ V（G）∪E（G）染不同的颜色.图G的k-无圈全染色是指图G的一种正常的k-全染色使得图G中任意一个圈上至少出现四种不同的颜色.图G的无圈全色数是指使得图G有一个正常的k-无圈全染色的最小的整数k,记作χa"（G）.本文研究的是图的无圈全染色问题,主要涉及到一些特殊图类、最大度Δ（G）≥ 8的平面图以及围长比较大的一般图.第一章,依次介绍了图论染色相关的一些基本概念及符号、全染色和无圈全染色的定义及研究现状,最后给出了本文的主要结论.第二章,证明了对于完全图和2-退化图,无圈全染色猜想成立.第三章,通过权转移方法证明了对于最大度△（G）≥8的平面图,无圈全染色猜想成立.第四章,研究了大围长图的无圈全染色,证明了如果图G的全色数χ"（G）)≤A,A为常数,那么对于任意的整数r,1 ≤ r≤2Δ（G）,都存在常数c>0,当g（G）≥cΔ（G）/rlogΔ2（G）/r,χa"（G）≤A+r.第五章,总结了本文的主要研究成果并做出了展望.

论文目录

• 致谢
• 摘要
• abstract
• 变量注释表
• 1 绪论
•   1.1 基本概念与符号
•   1.2 研究现状
•   1.3 论文主要结果
• 2 一些特殊图类的无圈圈全染色
•   2.1 完全图的无圈全染色
•   2.2 2-退化图的无圈全染色
• 3 平面图的无圈圈全染色
•   3.1 平面图的无圈全染色
• 4 大围长图的无圈全全染色
•   4.1 预备引理
•   4.2 主要结果和证明
• 5 总结与展望
•   5.1 总结
•   5.2 展望
• 参考文献
• 作者简历
• 学位论文数据集

文章来源

类型: 硕士论文

作者: 李晓亚

导师: 苗连英

关键词: 无圈全染色,平面图,围长,局部引理,权转移方法

来源: 中国矿业大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 中国矿业大学

分类号: O157.5

总页数: 51

文件大小: 1352K

下载量: 26