某些特殊图的点染色问题研究

发布时间：2017-08-08 20:05

  本文关键词：某些特殊图的点染色问题研究

  更多相关文章： 5-可染的 (1 1 1 1)-可染的 1-平面图 4-圈

【摘要】：图论是现代数学的重要分支之一,图的染色问题是图论中的热点也是难点.图的染色问题起源于著名的“四色定理”,即给平面上的任何一张地图着色,使得有公共边界的国家染上不同的颜色,至多使用四种颜色([1-3]).后来,有些学者将平面图的染色问题扩展到1-平面图的染色研究.一个图称为是1-平面的当且仅当它可以画在一个平面上,使得它的任何一条边最多交叉另外一条边.1984年,Bordin证明了1-平面图是6-可染的.1976年,Steinberg提出猜想：不含4-圈和5-圈的平面图是3-可染的.为了证明Steinberg猜想,学者把平面图的正常点染色推广到非正常点染色,Xu证明了不含4-圈和5-圈的平面图是(1,1,0)-可染的；Hill证明了不含4-圈和6-圈的平面图是(3,0,0)-可染的；Xu证明了不含4-圈和6-圈的平面图是(1,1,0)-可染的；Wang证明了不含4-圈和6-圈的平面图是(2,0,0)-可染的等等.2011年,Chang研究了Steinberg猜想并考虑了附近的染色.1986年L. Cowen提出了图的缺陷染色.图G的点染色是对图G的顶点集的一种剖分.如果图G的顶点集V可以剖分成互不相交的k个部分,给每一部分染上同一种颜色并且使得每部分的生成子图满足某种要求.若剖分产生的各部分都是点独立集,则为图G的正常点染色,否则称为图G的非正常点染色.如果对每部分剖分的导出子图中顶点的度数做限制,使得G[Vi]中所有顶点的度均不超过di,则称图G是(d1,d2,…,dk)-可染的.图G的k染色是指图G能够正常点染色所需要的色数至少为k.如果图G有一个k染色,又称图G是k-可染的.关于图的正常点染色,主要有以下结果：(1)[四色定理]平面图是4-可染的；(2)1-平面图是6-可染的([4])；(3) [Steinberg猜想[5]]不含4-圈和5-圈的平面图是3-可染的；(4)若图G为平面图,且不含长度为4,5,6,7的圈,则图G是3-可染的([13])；(5)若图G为平面图,且不含长度为4,5,6,8的圈,则图G是3-可染的([14])；(6)若图G为平面图,且不含长度为4,5,6,9的圈,则图G是3-可染的([15])；(7)若图G为平面图,且不含长度为4,5,7,8的圈,则图G是3-可染的([16])；(8)若图G为平面图,且不含长度为4,6,7,8的圈,则图G是3-可染的([17])；(9)若图G为平面图,且不含长度为4,6,8,9的圈,则图G是3-可染的([18])；(10)若图G为平面图,且不含长度为4,7,8,9的圈,则图G是3-可染的([19])；此外,Bordin等人在([20-26])中也研究了平面图的3-可染性.关于图的对每个剖分中点的度数做限制的非正常点染色,主要有以下结果：(1)若图G为平面图,且不含4-圈和5-圈,则图G是(1,1,0)-可染的([6])；(2)若图G为平面图,且不含4-圈和5-圈,则图G是(3,0,0)-可染的([7])；(3)若图G为平面图,且不含4-圈和6-圈,则图G是(1,1,0)-可染的([8])；(4)若图G为平面图,且不含4-圈和6-圈,则图G是(2,0,0)-可染的([10])；基于目前对图的点染色的研究,本人跟随前面学者的脚步,继续对图的染色问题进行研究.在第一章主要介绍了论文中所涉及的一些概念和术语符号以及本文的研究背景和已有的一些结果.在第二章中,我们仍然考虑传统的正常点染色问题,但我们将平面图的正常点染色研究推广到1-平面图的正常点染色研究Bordin证明了1-平面图是6-可染的,本文考虑不含4-圈且5-点不与5-点相邻的1-平面图的点染色,得到下面的结果：定理1.如果图G是1-平面图,满足：(1)图G不包含4-圈;(2)图G中5-点不与5-点相邻.那么图G是5-可染的.定理1是在1-平面图的正常点染色中,限制掉图中的4-圈,满足5-点不与5-点相邻,将1-平面图的正常点染色色数由6降到5.证明过程我们使用的是平面图的Euler公式,利用权转移的方法进行证明得出结果.在第三章中,我们将平面图的点染色研究推广到1-平面图的点染色研究,由正常的点染色问题研究推广到对每个剖分的生成子图中顶点的度数做限制的退化点染色研究.受XLuo, M. Chen, Wang等人在参考文献[17][18][19]中研究的启发,本文考虑的是不含3,4,5圈的1-平面图的退化点染色.得到下面的结果：定理2.不含3,4,5圈的1-平面图是(1,1,1,1)-可染的；定理2将1-平面图的正常点染色推广到不含某些结构的1-平面图的退化点染色,将每个色集的点导出子图由正常染色的点独立集放松到点导出子图中顶点的度数均不大于1.色数由6降到4.在第四章中,我们提出了一种新的非正常点染色.在这种非正常点染色中,我们没有对单色集的导出子图中顶点的度数做限制,而是使得单色集的导出子图中不含长度为l的圈.基于我们在第二、三章中对图的染色问题的讨论,不难发现,很多图的染色问题需要限制掉某些长度的圈,所以我们提出的新问题对图论中染色问题的研究具有一定的意义.定义：图G=(V, E)为有限图,给图G的顶点一个恰当的颜色分配,使得每个色类的导出子图不含长为l的圈,满足上述染色条件的最小的色数称为图G的最小无l圈点色数,记作χct-f(G).本文主要考虑最大度较小的情况下,使得剖分中不含长为3-圈和4-圈非正常点染色.得到如下结果：定理3.△≤4时,若G≠K5,χc3-f(G)≤2.定理4.△≤4时,χc4-f(G)=2.
【关键词】：5-可染的 (1 1 1 1)-可染的 1-平面图 4-圈
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 中文摘要6-10
• 英文摘要10-15
• 第一章 引言15-22
• 1.1 基本概念15-17
• 1.2 染色问题的研究现状17-20
• 1.3 本文的主要结果20-22
• 第二章 某些不含4圈的1-平面图是5-可染的22-33
• 2.1 预备知识22-23
• 2.2 结构性质23
• 2.3 定理1的证明23-33
• 第三章 不含3,4,5圈的1-平面图是(1,1,1,1)-可染的33-44
• 3.1 预备知识33-34
• 3.2 结构性质34-35
• 3.3 定理2的证明35-44
• 第四章 某些特殊图的非正常点染色44-52
• 4.1 预备知识44
• 4.2 定理3和4的证明44-52
• 参考文献52-56
• 攻读学位期间发表的学术论文56-57
• 致谢57

【参考文献】

中国期刊全文数据库 前3条

1 徐灵姬;王应前;;既不含4-圈又不含6-圈的平面图的非正常染色[J];中国科学:数学;2013年01期

2 张欣;刘桂真;吴建良;;不含3-圈的1-平面图的边染色[J];山东大学学报(理学版);2010年06期

3 ;A 3-color Theorem on Plane Graphs without 5-circuits[J];Acta Mathematica Sinica(English Series);2007年06期

，

本文编号：641769