圖的若干染色問(wèn)題研究.pdf

1、用G=(V,E)表示頂點(diǎn)集為V，邊集為E的圖，而圖的最大度，最小度分別用△，δ表示.若G是平面圖，常用F表示它的面集.若V∪E中的元素能用k種顏色進(jìn)行染色，使得任意兩個(gè)相鄰或相關(guān)聯(lián)的元素染有不同的顏色,則稱G是k-全可染的.用x11(G)來(lái)表示圖G的全色數(shù)，即使得G有k-全染色的最小的正整數(shù)k.顯然，對(duì)每個(gè)圖進(jìn)行全染色，至少需要△(G)+1個(gè)色.圖G的一個(gè)正常頂點(diǎn)k-染色是指一個(gè)映射φ:V→{1，…,k}，使得對(duì)任意uv∈E(G)，滿足

2、φ(u)≠φ(v).若G有k-染色，則稱G是k-可染的.用x(G)來(lái)表示圖G的點(diǎn)色數(shù)，即使得G有k-染色的最小的正整數(shù)k.現(xiàn)在給G的每個(gè)頂點(diǎn)v分配一個(gè)顏色集合L(v)，則稱L={L(v)/v∈V}是G的一個(gè)色列表.若對(duì)(V)v∈G，都能從其相應(yīng)的色列表L(v)中選取一個(gè)顏色φ(v)染給υ，使得(V)uv∈E(G)，有φ(u)≠φ(v)，則稱G是L-可染的.若G對(duì)任意一個(gè)滿足|L(v)|≥k的色列表L,G都是L-可染的，則稱G是k-列表可

3、染的，也稱G是k-可選擇的.用ch(G)來(lái)表示圖G的選擇數(shù)，即使得G是k-可選擇的最小的正整數(shù)k.圖G的一個(gè)線性k-染色是指G的一個(gè)正常頂點(diǎn)k-染色滿足任意兩種顏色的點(diǎn)導(dǎo)出子圖是點(diǎn)不交的路的并.用1c(G)來(lái)表示圖G的線性色數(shù)，即使得G有一個(gè)線性k-染色的最小的正整數(shù)k.
　　 本文在前人的工作基礎(chǔ)上，主要研究了圖的這三種染色問(wèn)題.
　　 論文分為四章，第一章主要是對(duì)本學(xué)位論文所涉及的問(wèn)題，背景，定義及全染色，3-列表染

4、色，線性染色的研究現(xiàn)狀進(jìn)行了一個(gè)綜述.
　　 第二章主要研究了平面圖的全染色的問(wèn)題.關(guān)于圖的全染色,有以下著名的猜想(Total Coloring Conjecture):對(duì)任意圖G，x″(G)≤△(G)+2.猜想主要由Vizing和Behzad等人獨(dú)立提出，簡(jiǎn)稱TCC，但是隨著研究的深入，人們發(fā)現(xiàn)許多圖不僅僅是滿足TCC的.更進(jìn)一步地，很多圖的全色數(shù)是可以取到下界△(G)+1的.對(duì)此，王應(yīng)前老師提出了平面圖上的全染色猜想:對(duì)每

5、個(gè)△(G)≥4的平面圖G，x″(G)=△(G)+1.本章主要研究了最大度至少為6且不含帶弦5圈和帶弦6圈的平面圖的全染色.
　　 第三章主要研究了平面圖的3-列表染色問(wèn)題.關(guān)于圖的3-列表染色，是在3-染色的基礎(chǔ)上展開(kāi)研究的.Steinberge猜想指出不含4，5圈的平面圖是3-可染的.一個(gè)自然的問(wèn)題就是不含4，5圈的平面圖是否是3-列表可染的呢？對(duì)此，Vogit給出了不含4，5圈但非3-列表可染的例子.Montassier提出