论文部分内容阅读
本论文所考虑的图均为简单的有限的无向图,设G是一个图,我们用V(G),|G|,E(G),e(G),△(G),δ(G)和g(G)分别表示G的项点集合,阶(顶点数),边集合,边数,最大度,最小度和围长.在不引起混淆的情况下,△(G),δ(G)和g(G)可分别简记为△,δ和g.图G的一个k—顶点染色,是指k种颜色1,2…,k对于G的各个顶点的一个分配;如果任意两个相邻顶点都分配到不同的颜色,称染色是正常的,设φ是图G的一个正常的顶点染色,若φ的任何两种不同颜色所染的顶点数目至多相差1,称φ是G的一个均匀染色.如果φ是图G的一个均匀k—顶点染色,称φ是G的一个均匀k—染色.图G可进行均匀k—染色的最小整数k称为G的均匀色数,记为Xe(G).
W.Meyer在[1]中证明了任意树T都存在均匀([△(T)/2]+1)—染色,Eggleton后来改进了W.Meyer证明过程,并证明了树T对于任意整数k≥[△(T)/2]+1,都存在均匀k—染色.W.Meyer基于其证明结果提出了以下均匀染色猜想(ECC):
猜想1:对于任意一个既不是完全图也不是奇圈的连通图G,有Xe(G)≤△(G).
Hajnal和Szemerédi[2]证明了:任意图G,对于任意的整数k≥△(G)+1,都存在均匀k—染色.
Chen,Lih和Wu[4]证明了:如果图G是一个连通图,且既不是完全图,奇圈又不是完全二部图K2m+1,2m+1,△(G)=△>|G|/2,那么G存在均匀△—染色.基于这一结果,Chen,Lih和Wu提出了以下E△CC猜想,可以算是ECC的改进形式:
猜想2:如果G是一个连通图,且既不是完全图,奇圈又不是完全二部图K2m+1,2m+1,△(C)=△,那么G存在均匀△—染色.
从这个猜想我们可以认为,它等价于Xe(G)≥△,它的结果包含了ECC的结论,如果说ECC是正确的,那么E△CC就足关于非正则图的结论.
Chen和Lih[5]证明了:
(1)T是一棵树,如果t≥3△(T)—8,或者t=3△(T)—10,那么T存在均匀3—染色;
(2)T=T(X.Y)是一棵非空的树,如果‖X|—|Y‖≤1,那么对所有的k≥2,T存在均匀k—染色:
(3)如果‖X|—|Y‖>1,那么T存在均匀k—染色当且仅当k≥ max{3,[(|T|+1)/(α(T—N|υ|)+2)]),其中υ是T的任意一个最大度点.
Lih和Wu[6]证明了:如果图G是一个连通的非完全的二部图,那么有Xe(G)≤△(C);完全二部图Kn,n存在均匀k—染色当且仅当[n/[k/2]]—[n/[k/2]]≤1;图G(X,Y)是一个具有ε条边的连通的二部图,若|X|=m≥n=|Y|,ε<[m/(n+1)](m—n)+2m,那么有Xe(G)≤[m/(n+1)]+1.
H.P.Yap和Y.Zhang在[7]中证明了:如果图G是一个连通的外平面图,△≥3,那么图G存在均匀△—染色;
Y.Zhang,H.P.Yap在|10|中证明了以下定理:任意平面图G,△(G)≥13,对任意整数m≥△(G),都存在均匀m—染色.
本论文主要讨论了均匀染色的背景,并且证明了以下的主要结果:
1.最大度△≥8,围长g≥5的平面图G存在均匀△—染色.
2.最大度△≥5,围长g≥12的平面图G存在均匀△—染色.
3.设G是一个不含4,5—圈的平面图,△≥9,那么G存在均匀△—染色.
4.一些图类的平方图的均匀染色的讨论.
5.一些图类的Mycielski图的均匀染色.