论文部分内容阅读
本论文所考虑的图均为简单的有限的无向图，设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图的均匀染色.