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