圖的均勻點染色與均勻全染色.pdf

1、圖的染色理論在圖論中具有非常重要的地位。圖的均勻染色作為染色理論的一種特殊情況，在1973年就已經(jīng)被提出，它被廣泛地運(yùn)用于生物學(xué)，電子學(xué)，工業(yè)生產(chǎn)及企業(yè)管理等領(lǐng)域，尤其在時間表，剖分，承載平衡等問題中有廣泛的應(yīng)用。近幾年來，圖的均勻染色的研究逐漸得到關(guān)注，并拓展出了許多分支，包括:均勻邊染色，均勻全染色，均勻列表染色等。本研究分為四個部分：
　　第一章：主要對本論文中所涉及的一些基本概念和符號作一些說明，同時對本方向的研究背景和研

2、究概況作一個綜述。
　　第二章：主要研究了不含4-和5-圈的平面圖的均勻染色.在Hajnal和Szemerédi證明了圖的均勻色數(shù)小于或者等于△+1后，1994年Chen，Lih和Wu提出猜想:不為Kn，C2n+1和K2n+1，2n+1的連通圖G是均勻△-可染的.Chen，Kierstead等人相繼證明了這個猜想對于△≤4的圖是成立的.2008年，朱俊蕾和卜月華驗證了這個猜想對△≥7且不含4-和5-圈的平面圖成立的.而在這章中，我

3、們運(yùn)用細(xì)致的結(jié)構(gòu)分析和經(jīng)典的權(quán)轉(zhuǎn)移方法證明了5≤△≤6且不含4-和5-圈的平面圖是均勻△-可染的.從而我們可以得到猜想對不含4-和5-圈的平面圖是成立的。
　　第三章：主要研究了環(huán)面圖的均勻染色.1998年，Zhang和Yap證明了每一個△≥13的平面圖有一個均勻△-染色.2012年，Nakpraist通過取邊-極小反例的方法證明了9≤△≤12的平面圖是均勻△-可染的.因此每一個△≥9的平面圖是均勻△-可染的.隨后，它用相同的方法

4、證明了△≥6且沒有3-圈，△≥7且沒有4-圈，△≥5且圍長不小于5的平面圖是均勻△-可染的.本章旨在將這些結(jié)果推廣到環(huán)面圖上.證明了△≥12的環(huán)面圖，△≥7且不含4-圈的環(huán)面圖，△≥9且不含5-圈的環(huán)面圖是均勻△-可染。
　　第四章：研究了△≤3的圖的均勻全染色。1994年，F(xiàn)u提出猜想:每一個圖G是均勻全后-可染的，k≥max{x"(G)，△+2}.2002年，Wang證明了每一個△≤3的重圖有一個均勻全5-染色.在這章中，我們