论文部分内容阅读
图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.