图的无圈全染色和无圈边染色

论文摘要

图的染色问题是一个非常活跃的研究课题,近年来,因为染色的规则和对象不同,图的染色理论也日益丰富.在本论文中我们主要研究图的无圈全染色和无圈边染色问题.如果φ是图G的一个正常的全染色,并且它能使图G的每一个圈中都至少包含4种颜色,那么就把φ定义为图G的无圈全染色.使图G的一个正常k-无圈全染色存在所需的最小的正整数k,就称作图G的无圈全色数,记为χa"（G）.Sun和Wu首先提出了图的无圈全染色的概念,并给出猜想:对任意的图G,满足Δ（G）+1≤χa"（G）≤Δ（G）+2.如果φ是图G的一个正常的边染色,并且它能使图G中不包含双色圈,那么就把φ定义为图G的无圈边染色.使图G的一个正常k-无圈边染色存在所需的最小的正整数k,称作图G的无圈边色数,用χa’（G）来表示.在2001年,Alon等人给出了无圈边染色的猜想,即:对任意图G,A（G）≤χa’（G）≤Δ（G）+2.有关无圈染色的猜想对我们的研究提供了非常重要的参考意义.本论文主要讨论了伪Halin-图和不含K4-minor的图的无圈全染色,以及不含3-圈的IC-平面图的无圈边染色问题.第一章,介绍了图论的研究背景,相关概念,以及目前的研究现状.第二章,利用极小反例的方法对伪Halin-图的无圈全染色问题进行了研究,证明:如果图G为伪Halin-图,那么（?）其中w是一个邻点全部位于边界的内点,并且有且仅有一个非正则邻点.第三章,对于不含K4-minor的图的无圈全染色问题,采用极小反例的方法证明:如果图G为不含K4-minor的图,那么（?）其中结构（*）为:两个3-圈xx1zx和yy1zy,并且d（z）=4,以及d（x1）=d（y1）=2.第四章,研究了不包含3-圈的IC平面图的无圈边染色问题,利用差值转移的方法和极小反例的方法,证明:如果图G为不包含3-圈的IC-平面图,那么χa’（G）≤Δ+7.第五章,对本文的结果进行了总结,并对后续问题作了一些展望.

论文目录

文章来源

类型: 硕士论文

作者: 徐靖

导师: 苗连英

关键词: 无圈全染色,无圈边染色,平面图,伪图

来源: 中国矿业大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 中国矿业大学

分类号: O157.5

总页数: 42

文件大小: 900K

下载量: 24

相关论文文献

• [1].蚂蚁为什么不会迷路?[J]. 科普童话 2017(10)
• [2].痒[J]. 厦门文学 2017(07)
• [3].神奇的镜子[J]. 小雪花(小学快乐作文) 2017(09)
• [4].同阶双轨道连通图的超圈边连通性[J]. 上海大学学报(自然科学版) 2017(02)
• [5].路的三类积的无圈边染色[J]. 宁夏师范学院学报 2017(03)
• [6].变换图G~(++-)的圈边连通性（英文）[J]. 兰州大学学报(自然科学版) 2016(03)
• [7].他山之桑 可以成链——记鄞州湾底村[J]. 百姓 2009(05)
• [8].不含特殊短圈平面图的无圈边染色[J]. 浙江师范大学学报(自然科学版) 2012(01)
• [9].不含4圈的平面图的无圈边染色[J]. 山东大学学报(理学版) 2012(06)
• [10].一些平面图的无圈边染色[J]. 山东大学学报(理学版) 2008(09)
• [11].不含3,4圈的平面图的无圈边染色的一个结果[J]. 贵州师范大学学报(自然科学版) 2014(01)
• [12].不含三角形的轮胎图的无圈边染色[J]. 山东大学学报(理学版) 2014(04)
• [13].不含相交三角形平面图无圈边染色[J]. 内江师范学院学报 2012(02)
• [14].平面图无圈边着色的一个结果[J]. 重庆工商大学学报(自然科学版) 2012(04)
• [15].不含相交三角形和4圈的平面图的无圈边染色[J]. 苏州科技学院学报(自然科学版) 2012(02)
• [16].不含5-圈的平面图的无圈边着色[J]. 纯粹数学与应用数学 2012(03)
• [17].不含短圈平面图的无圈边染色的一个结果[J]. 贵州师范学院学报 2012(06)
• [18].特殊积图的无圈边染色[J]. 襄樊学院学报 2012(05)
• [19].最大度为4的图的无圈边染色[J]. 青岛科技大学学报(自然科学版) 2011(02)
• [20].图的无圈边染色的一个结果[J]. 黑龙江科技学院学报 2010(04)
• [21].不含3圈的平面图的无圈边染色[J]. 贵州大学学报(自然科学版) 2013(05)
• [22].平面图的无圈边染色[J]. 江苏师范大学学报(自然科学版) 2014(03)
• [23].笛卡尔图的无圈边染色[J]. 齐齐哈尔大学学报(自然科学版) 2017(06)
• [24].不含三角形的平面图的无圈边染色[J]. 烟台大学学报(自然科学与工程版) 2013(04)
• [25].平面图和系列平行图的无圈边染色[J]. 中国科学(A辑:数学) 2008(12)
• [26].一类Mycielski图的点可区别均匀无圈边染色[J]. 西北民族大学学报(自然科学版) 2012(03)
• [27].图的邻点可区别无圈边染色[J]. 科技信息 2011(23)
• [28].图的邻点可区别无圈边染色的一个界[J]. 系统科学与数学 2008(10)
• [29].平面图的无圈边染色[J]. 淮阴师范学院学报(自然科学版) 2011(05)
• [30].基于最大平均度的图的无圈边染色[J]. 信阳师范学院学报(自然科学版) 2012(02)

标签：无圈全染色论文;  无圈边染色论文;  平面图论文;  伪图论文;