论文部分内容阅读
本文考虑的图均为有限简单图.给定一个图G,我们将G的顶点集、边集、最大度、最小度、最大平均度及边e,e间的距离分别记作V(G),E(G),△(G),δ(G),mad(G)和dG(e,e). 若图G存在一个同构图G,其中G的顶点均在同一个平面内,而G的边只能在端点处相交,则称G为平面图.在平面图G中,用F(G)来表示G的面集. 设映射ψ:E(G)→{1,2,…,k}.若e,e∈E的距离至多为2,有ψ(e)≠ψ(e),则称ψ是G的一个强k-边染色.若G有一个强k-边染色,则称图G是强k-边可染的,且把xs(G)=min{k|G有一个强k-边染色}称为G的强边色数. 对于图的强边色数,1989年,Erd(o)s和Ne(s)etril提出了关于其上界的一个著名的猜想.设图G的最大度为△,则(1)若△为偶数,则xs(G)≤5/4△2;(2)若△为奇数,则xs(G)≤1/4(5△2-2△+1).对于这个猜想,学者们做了大量的研究工作,得出了很多重要的结果. 本文在已有的研究基础上,主要研究了不含部分短圈的平面图的强边色数及限制图的最大平均度时的强边色数,共分为四个章节.本文的第一章主要介绍了一些相关的概念,并对强边染色的研究现状和可研究的问题做了概括.第二章主要研究了围长大于等于7的平面图以及围长大于等于5的平面图的强边染色.第三章主要讨论了△(G)=4的图的强边染色,在分别给图G的最大平均度一个限制条件下,得出了G的强边色数的上界.第四章证明了不含若干短圈的△(G)=4的平面图,其强边色数的上界为19.