1-平面图的无圈边染色数

发布时间：2017-11-23 14:22

  本文关键词：1-平面图的无圈边染色数

  更多相关文章： 无圈边染色 无圈边染色数 1-平面图

【摘要】：图G的无圈k-边染色是指图G的一个正常边染色且不产生双色圈的k-边染色.图G的无圈边染色数χa'(G)是使得图G有一个无圈k-边染色的最小整数k.在1978年,Fiamcik提出了任意图的无圈边染色数不超过△(G)+ 2的猜想,△(G)表示图G的最大度.在2001年,Alon等人又一次在文献中陈述了这个猜想.研究者们称这个猜想为"无圈边染色猜想",简记为"AECC".图G是k-闭极小图,是指最大度不超过k的图G,其任意真子图H都满足χa'(G)且χa'(H)≤k.图G是1-平面图,是指它可以画在平面上使得每一条边至多与一条其他的边相交.图G是平面图,是指它可以画在平面上使得每一条边都不与其他的边相交.很明显平面图符合1-平面图的定义,即平面图都是1-平面图.本论文共证明了两个结论,一个是不含三角形的1-平面图G,无圈边染色数χa'(G)≤A(G)+ 14.另一个是满足围长至少为5的1-平面图G,无圈边染色数χa'(G)≤△(G)+7.论文内容共分为五章.第一章是引言,介绍图论的起源,图论起源于非常经典的哥尼斯堡七桥问题.介绍图论的历史发展,图的染色问题的意义,图的无圈边染色相关概念的产生,并对论文的主要内容进行简要介绍.第二章是基础知识,阐述全文将要用到的一些基本概念和符号,以及一些关于图的无圈边染色数的研究成果.按照研究对象分为围长比较大的图,正则图,最大平均度比较小的图,最大度比较小的图,1-平面图,平面图,围长比较大的平面图,不含短圈相互关联的平面图,不含短圈的平面图,外平面图这些类进行介绍.第三章是一些结构引理,主要是为后面两章的证明做准备.第四章是要证明的第一个结果,在已有1-平面图无圈边染色数结论的基础上,结合已知的结构引理,改进了Wang等人证明的结果,即不含三角形的1-平面图的无圈边染色数不超过△+ 17,本篇文章用权转移方法证明了不含三角形的1-平面图的无圈边染色数不超过△ + 14.第五章是要证明的第二个结果,通过添加围长条件并结合已知的结构引理,证明了围长至少为5的1-平面图的无圈边染色数上界为△ + 7.
【学位授予单位】：河南大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5

【参考文献】

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

1 Wen Yao SONG;Lian Ying MIAO;;Acyclic Edge Coloring of Triangle-free 1-planar Graphs[J];Acta Mathematica Sinica;2015年10期

2 WAN Min;XU BaoGang;;Acyclic edge coloring of planar graphs without adjacent cycles[J];Science China(Mathematics);2014年02期

3 王维凡;舒巧君;;没有K_4-图子式的图的无圈边色数[J];中国科学:数学;2011年08期

4 ;Acyclic edge colorings of planar graphs and series-parallel graphs[J];Science in China(Series A:Mathematics);2009年03期

，

本文编号：1218689