论文部分内容阅读
本文讨论的图均为简单无向有限的平面图。对于一个图G=G(V(G),E(G)),V(G),E(G)分别表示其顶点集合和边的集合。对于顶点v∈V(G),我们用d(v)表示其度数,△(G)和δ(G)分别表示G中顶点的最大度和最小度,简记为△和δ。在图论符号中我们常略去字母G分别用V,E,v和ε代替V(G),E(G),v(G),ε(G)。
图的染色问题,是图论的主要研究问题之一。图的染色一般分为边染色、点染色、全染色以及其它特定染色。本文讨论了平面图的边染色问题,证明了两个主要结论。
图G的一个k-边正常染色是指k种颜色在E(G)上的一种分配,使得相邻的两条边染以不同的颜色。若图G有一个k-边正常染色,则称G是k-边可染色的。图G的边色数是指使G为k-边可染色的最小值k,记为x(G)。
边染色问题有下面的著名定理:
Vizing定理(1964)设G是无环的非空简单图,则△(G)≤x(G)≤△(G)+1。
对于有重边的图G,设μ(G)表示G中边的最大重数,Vizing定理实际上证明了一个更一般的结论:△(G)≤x(G)≤△(G)+μ(G)。
Vizing定理提出了图的一个分类问题:若图G满足x(G)=△(G),则称G为第一类图;若图G满足:x(G)=△(G)+1,则称G为第二类图。确定一个图属于第一类还是第二类是很困难,目前仅对少量图判明了它们所属的类。路、树、二部图、偶数阶完全图,轮图都是第一类图;奇圈、奇数阶完全图都是第二类图。一般情况下一个图属于第几类图,尚没有好的充分必要的判别条件。已经知道存在最大度是2、3、4、5的第二类平面图,且Vizing(1965)已证明:不存在最大度≥8的第二类平面图。Sanders and Zhao[1]证明了最大度为7的平面图是边染色第一类图。目前尚不知道是否存在最大度为6的第二类平面图。
在本文中我们主要研究平面图的边染色问题,其中短圈是指长度小于等于5的圈。我们通过对顶点和面上的值进行重新分配,运用欧拉公式证明了:若G是△(G)=6的平面图,且G中不含相邻的短圈,则x(G)=6;若G是△(G)=5的平面图,且G中不含相交的3-圈与短圈,则x(G)=5,即G是第一类图。