幾類圖的均勻染色.pdf

1、本論文所考慮的圖均為簡單的有限的無向圖，設(shè)G是一個圖，我們用V（G），｜G｜，E（G），e（G），△（G），δ（G）和g（G）分別表示G的項點集合，階（頂點數(shù)），邊集合，邊數(shù)，最大度，最小度和圍長.在不引起混淆的情況下，△（G），δ（G）和g（G）可分別簡記為△，δ和g.圖G的一個k—頂點染色，是指k種顏色1，2…，k對于G的各個頂點的一個分配；如果任意兩個相鄰頂點都分配到不同的顏色，稱染色是正常的，設(shè)φ是圖G的一個正常的頂點染色，若φ

2、的任何兩種不同顏色所染的頂點數(shù)目至多相差1，稱φ是G的一個均勻染色.如果φ是圖G的一個均勻k—頂點染色，稱φ是G的一個均勻k—染色.圖G可進行均勻k—染色的最小整數(shù)k稱為G的均勻色數(shù)，記為Xe（G）. W.Meyer在[1]中證明了任意樹T都存在均勻（[△（T）/2]+1）—染色，Eggleton后來改進了W.Meyer證明過程，并證明了樹T對于任意整數(shù)k≥[△（T）/2]+1，都存在均勻k—染色.W.Meyer基于其證明結(jié)果

3、提出了以下均勻染色猜想（ECC）： 猜想1：對于任意一個既不是完全圖也不是奇圈的連通圖G，有Xe（G）≤△（G）. Hajnal和Szemerédi[2]證明了：任意圖G，對于任意的整數(shù)k≥△（G）+1，都存在均勻k—染色. Chen，Lih和Wu[4]證明了：如果圖G是一個連通圖，且既不是完全圖，奇圈又不是完全二部圖K2m+1，2m+1，△（G）=△>｜G｜/2，那么G存在均勻△—染色.基于這一結(jié)果，Che

4、n，Lih和Wu提出了以下E△CC猜想，可以算是ECC的改進形式： 猜想2：如果G是一個連通圖，且既不是完全圖，奇圈又不是完全二部圖K2m+1，2m+1，△（C）=△，那么G存在均勻△—染色. 從這個猜想我們可以認為，它等價于Xe（G）≥△，它的結(jié)果包含了ECC的結(jié)論，如果說ECC是正確的，那么E△CC就足關(guān)于非正則圖的結(jié)論. Chen和Lih[5]證明了： （1）T是一棵樹，如果t≥3△（T）—8，或

5、者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）；完全二部圖

6、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，△

7、（G）≥13，對任意整數(shù)m≥△（G），都存在均勻m—染色. 本論文主要討論了均勻染色的背景，并且證明了以下的主要結(jié)果： 1.最大度△≥8，圍長g≥5的平面圖G存在均勻△—染色. 2.最大度△≥5，圍長g≥12的平面圖G存在均勻△—染色. 3.設(shè)G是一個不含4，5—圈的平面圖，△≥9，那么G存在均勻△—染色. 4.一些圖類的平方圖的均勻染色的討論. 5.一些圖類的Mycielski圖的均勻染