圖的染色問題及其推廣.pdf

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

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

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

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

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

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

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

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