有限制條件的平面圖的均勻染色.pdf

1、　　設(shè)G是一個(gè)圖,圖G的一個(gè)頂點(diǎn)染色是指k種顏色1,2,…,k對G的各個(gè)頂點(diǎn)的一個(gè)分配,且G的任意兩個(gè)相鄰頂點(diǎn)都分配到不同的顏色,令Vi記顏色為i的頂點(diǎn)的集合,如果圖G的一個(gè)頂點(diǎn)染色對所有的i,j滿足‖Vi|-|Vj‖≤1,那么稱這一染色為圖G的一個(gè)均勻k-染色,圖G具有均勻k-染色的最小整數(shù)k稱為G的均勻色數(shù),記為Xe(G)。
　　W.Meyer[1]證明了：任意樹T都存在均勻(「Δ(T)/2(？)+1)-染色。并提出了以下猜想

2、：
　　猜想1：對于任意一個(gè)既不是完全圖也不是奇圈的連通圖G,有Xe(G)≤Δ(G)。
　　Hajnal和Szemerédi[2]較早地證明了：任意圖G,對于任意的整數(shù)k≥Δ(G)+1,都存在均勻k-染色。Yap和Zhang[10]證明了：最大度Δ≥13的任意平面圖G,對任意整數(shù)m≥Δ,都存在均勻m-染色。
　　Lih和Wu[6](Yap[12])證明了：如果圖G是一個(gè)連通的二部圖,且不是完全二部圖K2m+1,2m+1

3、,m≥0,那么G存在均勻Δ-染色。基于這一結(jié)果,Chen,Lih和Wu提出了以下猜想：
　　猜想2：如果圖G是一個(gè)既不是完全圖,奇圈又不是完全二部圖K2m+1,2m+1,m≥0的連通圖,那么G存在均勻Δ-染色。
　　Yap和Zhang在[7]中證明了最大度Δ≥3的連通的外平面圖G存在均勻Δ-染色；在[9]中證明了：最大度Δ≥|G|/3+1的圖G存在均勻Δ-染色。
　　本論文首先敘述了與均勻染色相關(guān)的一些背景知識,第二,