圖的均勻點(diǎn)染色與均勻全染色.pdf

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

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

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

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