圖的染色問(wèn)題及其推廣.pdf

1、本文主要研究有關(guān)有限無(wú)向簡(jiǎn)單圖的染色相關(guān)的一些問(wèn)題.
　　 圖G的一個(gè)正常頂點(diǎn)染色是指k種顏色1,2,…,k對(duì)于G的各頂點(diǎn)的一個(gè)分配,使得任意兩個(gè)相鄰的頂點(diǎn)分配以不同顏色.若圖G有一個(gè)正常k-點(diǎn)染色,那么就稱(chēng)圖G是k-點(diǎn)可染色的.圖G的色數(shù)是指G有一個(gè)正常k頂點(diǎn)染色的數(shù)k的最小值,用χ(G)表示.
　　 圖G的一個(gè)頂點(diǎn)色列表L是一個(gè)顏色集合簇,它指定G的每個(gè)頂點(diǎn)ν一個(gè)顏色集合L(ν).對(duì)于一個(gè)給定的色列表L，若G有一個(gè)正

2、常的頂點(diǎn)染色π,使得對(duì)每一個(gè)頂點(diǎn)ν∈V(G),有π(ν)∈L(ν),則稱(chēng)G為L(zhǎng)-頂點(diǎn)可染的或者稱(chēng)π是G的一個(gè)L-染色.若對(duì)每一個(gè)滿(mǎn)足｜L(ν)｜≥k,v∈V(G)的L,G都是L-點(diǎn)可染的,則稱(chēng)G是k-點(diǎn)列表可染的,簡(jiǎn)稱(chēng)G是k-列表可染的,或稱(chēng)為k-可選的.G的頂點(diǎn)列表色數(shù)χl(G)是使得G是k-可選擇的最小的非負(fù)整數(shù)尼.
　　 圖的列表染色是圖的染色的一個(gè)推廣,列表染色的概念首先由Vizing[68]和Erd(o)s等人[32]

3、在20世紀(jì)70年代提出.1979年,Erd(o)s,Rubin和Taylor[32]提出了下面的猜想.
　　 猜想1.2.1(Erd(o)s,RubinandTaylor[32])(1)每個(gè)平面圖是5-可選色的；(2)存在平面圖不是4-可選色的.
　　 從20世紀(jì)90年代以來(lái),大量的學(xué)者和專(zhuān)家對(duì)圖的選色問(wèn)題進(jìn)行了研究,并得出了一系列成果.上述的猜想分別由Thomassen于1994年[65]中及Voigt于1995年[6

4、9]中予以解決.所有的2-可選色的平面圖已由Erd(o)s,Rubin和Taylor在[32]中進(jìn)行了特征化的刻畫(huà).Gutner于1996年在文獻(xiàn)[36]中證明這類(lèi)著色問(wèn)題是NP-完全的.所以眾多學(xué)者轉(zhuǎn)向?qū)ふ乙粋€(gè)圖是3-可選色或4-可選色的充分條件.我們?cè)谡撐闹杏懻摿祟?lèi)似的問(wèn)題,進(jìn)一步得到了如下的結(jié)果.
　　 定理2.2.1.若G是一個(gè)無(wú)5-,6.和7-圈的平面圖,如果G中任意兩個(gè)三角形的距離至少為3,則G是3-可選色的.

5、>　　 定理2.2.2若G是一個(gè)無(wú)5-,6.和8-圈的平面圖,如果G中任意兩個(gè)三角形的距離至少為2,則G是3-可選色的.
　　 定理2.2.3若G是一個(gè)無(wú)4-,5-,7-和10.圈的輪胎圖,則G是3-可選色的.
　　 假若染色π是圖G的正常頂點(diǎn)染色,并且對(duì)于G中的任何一個(gè)圈子圖C都用到至少3種顏色,那么我們稱(chēng)染色π是G的一個(gè)無(wú)圈染色.圖G的無(wú)圈色數(shù)χa(G)就是使得G是無(wú)圈k-可染的最小的非負(fù)整數(shù)k.
　　 對(duì)

6、于一個(gè)給定的色列表L若G有一個(gè)正常的無(wú)圈染色7r,使得對(duì)每一個(gè)頂點(diǎn)ν∈V(G),都有π(ν)∈L(ν),則稱(chēng)G是無(wú)圈L-可染的或者稱(chēng)π是G的一個(gè)無(wú)圈L-染色。若對(duì)每一個(gè)滿(mǎn)足｜L(ν)｜≥k,ν∈V(G)的色列表L,G都是無(wú)圈L-可染的,則稱(chēng)G是無(wú)圈k-列表可染的,簡(jiǎn)稱(chēng)G是無(wú)圈k-可選的.G的無(wú)圈列表色數(shù)χla(G)是使得G是無(wú)圈k-列表可染的最小的非負(fù)整數(shù)k.
　　 在第3章中,我們討論了無(wú)指定圈的平面圖的無(wú)圈選色問(wèn)題,記一個(gè)弦

7、k-圈為一個(gè)帶弦的k-圈.我們給出了下述結(jié)果,此結(jié)果改進(jìn)了Montassier等人在([55],2006)及([59],2007)中的一些結(jié)果.
　　 定理3.2.1若G是一個(gè)無(wú)4-和弦6-圈的平面圖,則G是無(wú)圈5-可選色的.
　　 定理3.2.2若G是一個(gè)無(wú)4-和6-圈的輪胎圖,則G是無(wú)圈5-可選色的.
　　 推論3.2.1若G是一個(gè)無(wú)4-和5-圈,或無(wú)4-和6-圈,或無(wú)3-和4-圈的平面圖,則G是無(wú)圈5-可選

8、色的.
　　 每個(gè)分支均為路的圖稱(chēng)為線(xiàn)性森林,圖G的一個(gè)t-線(xiàn)性染色是指t種顏色1,2,…,t對(duì)于G的各條邊的一個(gè)分配,使得(V(G),φ-1(α))是一個(gè)線(xiàn)性森林,其中1≤α≤T.圖G的線(xiàn)性蔭度LA(G)定義為最小的整數(shù)T使得G有一個(gè)t-線(xiàn)性染色.
　　 本文第4章對(duì)非負(fù)歐拉特征值圖的亡.線(xiàn)性染色進(jìn)行了討論.首先給出了一個(gè)特殊非負(fù)特征值圖類(lèi)的結(jié)構(gòu)結(jié)論,運(yùn)用此結(jié)論,討論了此類(lèi)圖當(dāng)最大度較小時(shí)的線(xiàn)性蔭度值.