平面图的边染色问题

发布时间：2017-07-08 17:30

  本文关键词：平面图的边染色问题

  更多相关文章： 平面图 边染色 权转移方法

【摘要】：图G的k-边染色是用k种颜色对图G的边集合的元素进行着色,使得相邻的两条边染不同的颜色,即存在一个映射φ：E(G)→{1,2,...,k},对G中任意两条相邻的边e1和e2,有φ(e1)≠φ(e2).图G的边色数,用χ'(G)表示,是使G存在k-边染色的最小整数kVizing定理指出：对于任意简单图G,我们有χ'(G)=△(G)或△(G)+1.如果χ'(G)=△(G),图G称为第一类的,如果χ'(G)=△(G)+1,图G称为第二类的Vizing证明了△≥8的平面图是第一类的,并且提出著名的Vizing猜想：每个最大度不小于6的平面图是第一类的.对△=7的情形已由S anders和Zhao以及Zhang独立证明.因此,Vizing猜想只剩下△=6的情形还没有证明.Ni证明了最大度为6且不含弦-k-圈(4≤k≤7)的平面图是第一类的.我们证明了：最大度为6,且不含弦-8-圈的平面图是第一类的.利用反证法,假如存在最大度为6,且不含弦-8-圈的平面图G是第二类的,不妨设G是临界图,对任意x∈V(G)∪F(G),定义权函数为ch(x)=d(x)-4,得到所有顶点和面上的权值之和为-8,并设置了权值转移规则,在权值重新分配的过程中,所有顶点和面的权值之和保持不变,对所有的顶点和面上的权值进行重新分配后得到的新权值定义为ch',如果对任意的x∈V(G)∪F(G),都有ch'(x)≥0,就会得到矛盾：0≤∑x∈V(G)∪F(G)ch'(x)=∑x∈V(G)∪F(G)ch(x)=-80,从而证明不存在这样的反例.我们发现：对于最大度为6,且不含弦-8-圈的临界图,存在关联3-面的个数较多且关联6个面的度数之和较小的6-点,在权值转移的过程中,这类6-点传递给它的邻点以及它关联的3-面的权值之和大于这类6-点从它所关联的面上得到的权值之和,我们通过对这类6-点的某些邻点的结构进行研究,发现这些邻点所关联的面的度数较大,因此,在设置权转移规则时,可安排这类6-点从它的某些邻点上得值.权值重新分配后,我们验证了任意顶点和面上的权值都不小于0,反证法证明了我们的结论.2≤△≤5的平面图既有第一类图,也有第二类图,Ni证明了：最大度为5且不含弦-4-圈和弦-k-圈(k=5,6)的平面图是第一类的.我们证明了：最大度为5且不含弦-4-圈和弦-7-圈的平面图是第一类的.我们分别对最大度为5且不含弦-4-圈和弦-7-圈的临界图的每个顶点以及它的邻点所关联的面的情况进行研究,并给出了适当的定义和权转移规则,反证法证明了我们的结论.
【关键词】：平面图 边染色 权转移方法
【学位授予单位】：山东大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 中文摘要6-8
• 英文摘要8-10
• 第一章 绪论10-17
• §1.1 基本定义10-12
• §1.2 研究背景12-17
• 第二章 最大度为6且不含弦-8-圈的平面图的边染色问题17-34
• §2.1 结构与性质17-25
• §2.2 主要定理及其证明25-33
• §2.3 小结33-34
• 第三章 最大度为5且不含弦-4-圈和弦-7-圈的平面图的边染色问题34-45
• §3.1 结构与性质34-39
• §3.2 主要定理及其证明39-44
• §3.3 小结44-45
• 第四章 结论和展望45-47
• 参考文献47-50
• 致谢50-51
• 附表51

【相似文献】

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

1 卢建立;任凤霞;马美琳;;中间图的邻点强可区别全染色[J];河南师范大学学报(自然科学版);2012年05期

2 马生全,张忠辅,姚兵,李敬文;C_(3n)~2,C_(4n)~2邻点可区别的全染色[J];兰州铁道学院学报;2003年04期

3 李敬文;强会英;张忠辅;王文杰;王治文;;高度图的邻点可区别的全染色界的一点注[J];兰州交通大学学报;2006年01期

4 王颜妮;王丽伟;刘萍;;几类图的邻点可区别的全染色[J];科学技术与工程;2007年13期

5 王雅琴;刘西奎;王英;;一些图的邻点可区别关联着色[J];大学数学;2008年04期

6 刘海涛;;C_(5m)×C_(5n)图的邻点可区别的边染色[J];河西学院学报;2008年02期

7 卞西燕;苗连英;尚华辉;段春燕;马国翼;;图的邻点可区别边划分(英文)[J];华东师范大学学报(自然科学版);2009年04期

8 郑纯;刘焕平;;扇和轮的邻点强可区别全染色[J];哈尔滨师范大学自然科学学报;2009年05期

9 严谦泰;;k-方图的一般邻点可区别边染色[J];安徽大学学报(自然科学版);2010年03期

10 严谦泰;严楷;;关于图的一般邻点可区别边染色[J];数学的实践与认识;2010年24期

中国重要会议论文全文数据库 前3条

1 李莉;耿显民;;一类随机图的邻点度数和[A];第十一届中国不确定系统年会、第十五届中国青年信息与管理学者大会论文集[C];2013年

2 曹渊;郭永辉;王铁良;田宙;;自然邻点插值方法在材料状态方程数据库开发中的应用[A];中国计算力学大会'2010（CCCM2010）暨第八届南方计算力学学术会议（SCCM8）论文集[C];2010年

3 刘君;赵传成;任志国;包世堂;李敬文;张忠辅;;C_m·F_n的邻点可区别的边染色[A];中国运筹学会第七届学术交流会论文集（中卷）[C];2004年

中国博士学位论文全文数据库 前2条

1 孔海荣;区组长为4的二维不含邻点的平衡样本设计[D];河北师范大学;2008年

2 黄丹君;平面图的邻点可区别染色与点荫度[D];苏州大学;2012年

中国硕士学位论文全文数据库 前10条

1 刘配配;平面图的非正常染色[D];浙江师范大学;2015年

2 黄晨悦;一类区组长为5的一维不含邻点的平衡样本设计的存在性[D];河北师范大学;2016年

3 李晓丽;区组长为5的二维不含邻点的平衡样本设计[D];河北师范大学;2016年

4 张晓望;平面图的边染色问题[D];山东大学;2016年

5 李琼;图的一般邻点可区别色指标[D];西北师范大学;2008年

6 赵新梅;图的邻点可区别正常边染色的一些结果[D];西北师范大学;2006年

7 王雅琴;图的关联着色与邻点可区别关联着色[D];山东科技大学;2007年

8 刘萍;图的邻点可区别的全染色[D];山东师范大学;2008年

9 王倩;若干图的邻点可区别关联染色[D];西北民族大学;2011年

10 张彩霞;几类图的邻点可区别均匀E-全染色[D];兰州交通大学;2015年

，

本文编号：535618