1、圖的染色問題是圖論領(lǐng)域中一個經(jīng)典而且比較活躍的分支.圖的染色問題已由傳統(tǒng)的邊染色、點染色和全染色發(fā)展為種類繁多的新型染色問題，每種染色都有著各自重要的理論價值和適當(dāng)?shù)膽?yīng)用背景.這些新型染色問題在算法設(shè)計、時間排序問題以及資源分配問題中有著廣泛的應(yīng)用，這不僅產(chǎn)生了許多有趣的未解決問題，而且也促使研究方法不斷創(chuàng)新，從而極大地豐富了圖的染色理論.本文主要研究平面圖和1-平面圖的無圈列表(點)染色、正常邊染色、正常全染色、(p，1)-全染色以及

2、鄰點可區(qū)別全染色問題.
　　除非特殊說明，約定本文中所涉及到的圖均為有限、無向、簡單且非空的圖.給定圖G，用V(G)，E(G)，△(G)分別表示圖G的頂點集，邊集和最大度.v(G)=|V(G)|和e(G)=|E(G)|分別表示G的階數(shù)和邊數(shù).圖G的圍長是G中最短圈的長度，記為g(G).如果一個圈除了自身以外它相鄰一個3-圈，則稱此圈為三角化的;如果一個圈除了自身以外它相鄰一個4-圈，則稱此圈為四角化的.平面圖是指能夠嵌入到平面上使

3、得其任意兩條邊僅在端點處相交的圖，這樣的嵌入稱為平面嵌入，該平面嵌入稱為平圖.1-平面圖G是指G能夠嵌入到平面上使得G的任意一條邊最多被交叉一次.1-平面圖G按照上述條件的一種畫法稱為G的一種1-平面嵌入，此1-平面嵌入稱為1-平圖.所以1-平圖中的每個交叉點w都是由兩條邊相交所得，從而每個交叉點w都對應(yīng)著兩條相交邊，同時也對應(yīng)著由這兩條相交邊的四個端點組成的集合ψ(w).如果1-平面圖的一個1-平面嵌入中任意兩個交叉點w和w’滿足ψ(

4、w)∩ψ(w')=(θ)，則稱此1-平面圖為IC-平面圖.
　　給定圖G=(V(G)，E(G))，它的正常k-點染色是指一個映射φ:V(G)→{1，2，…，k}，使得圖G中任意兩個相鄰的頂點u和v滿足φ(u)≠φ(v).使得G具有正常k-點染色的最小正整數(shù)k稱為G的點色數(shù)，記為x(G).在圖G的一個正常點染色φ中，如果G中的每個圈上至少有三種顏色，則稱φ為圖G的無圈染色.如果給圖G的每個頂點v∈V(G)都分配一個顏色集合L(v)，

5、則稱L={L(v):v∈V(G)}為G的一個點列袁.給定點列表L,如果G中存在無圈染色φ使得每個頂點v的顏色滿足φ(v)∈L(v)，則稱圖G是無圈L-可染的.如果對任意點列表L圖G是無圈L-可染的，其中對任意點v∈V(G)有|L(v)|≥k，則稱圖G是無圈k-可選的.使得圖G是無圈k-可選的最小正整數(shù)k稱為G的無圈列表色數(shù)，記為xla(G).Borodin等人猜想:每個平面圖都是無圈5-可選的.我們主要討論具有相鄰3-圈的平面圖是無圈5

6、-可選或者無圈6-可選的充分條件.
　　圖G的一個正常k-邊染色是一個映射φ:E(G)→{1，2，…，k}，使得任意兩條相鄰的邊x，y∈E(G)滿足φ(x)≠φ(y).使得G具有正常k-邊染色的最小正整數(shù)k稱為圖G的邊色數(shù)，記為x'(G).著名Vizing定理證明每個簡單圖G的邊色數(shù)x'(G)要么等于最大度△(G)要么等于△(G)+1。這個定理將所有的圖分成了兩類:第一類圖滿足關(guān)系式x'(G)=△(G)，第二類圖滿足關(guān)系式x'(G

7、)=△(G)+1.如果連通圖G是第二類圖，并且對G中的任意邊e有不等式x'(G-e)＜x'(G)成立，則稱G是臨界圖.如果G是最大度為△的臨界圖，則稱G為△-臨界圖.張欣和吳建良證明了每個最大度至少為10的1-平面圖是第一類的.同時，張欣構(gòu)造了最大度為6或7的第二類的1-平面圖，隨后張欣和劉桂真提出了猜想:每個最大度至少為8的1-平面圖都是第一類的，我們證明了最大度至少為8的1-平面圖和最大度至少為7的IC-平面圖在限制弦圈的條件下是第

8、一類的.
　　圖G的一個正常k-全染色是一個映射φ:V(G)∪E(G)→{1，2，…，k}，使得任意兩個相鄰或關(guān)聯(lián)的元素x，y∈V(G)∪E(G)滿足φ(x)≠φ(y).使得G具有正常k-全染色的最小正整數(shù)k稱為圖G的全色數(shù)，記為x″(G).Behzad與Vizing分別獨立地提出了著名的全染色猜想:任意簡單圖G滿足x"(G)≤△(G)+2.根據(jù)1-平面圖的結(jié)構(gòu)特點和附加結(jié)構(gòu)特征，我們分別確定了最大度至少為9和最大度至少為12的1

9、-平面圖在圍長的限制條件下的全色數(shù)的上界.
　　圖G的k-(p，1)-全染色是從V(G)∪ E(G)到顏色集合{0，1，…，k}的映射φ，使得圖G中相鄰或相關(guān)聯(lián)的元素滿足以下條件:當(dāng)uv∈E(G)時，|φ(u)-φ(v)|≥1;當(dāng)邊e1和邊e2相鄰時，|φ(e1)-φ(e2)|≥1;當(dāng)頂點u和邊e關(guān)聯(lián)時，|φ(u)-φ(e)|≥p.使得圖G有k-(p，1)-全染色的最小正整數(shù)k稱為圖G的(p，1)-全色數(shù)，記為λTp(G).Hav

10、et和Yu提出了(p，1)-全染色猜想:任何圖G滿足λTp(G)≤ min{△(G)+2p-1，2△(G)+p-1}.通過分析結(jié)構(gòu)性質(zhì)，我們得到最大度至少為4p+4的平面圖和最大度至少為6p+3的特殊1-平面圖的(p，1)-全色數(shù)的上界.
　　在圖G的一個正常k-全染色φ中，令Cφ(v)表示頂點v的顏色及與其關(guān)聯(lián)的邊的顏色集合.如果圖G中的任意一條邊uv滿足Cφ(u)≠Cφ(v)，則稱這個正常k-全染色φ為鄰點可區(qū)別k-全染色.使

11、得G具有鄰點可區(qū)別k-全染色的最小正整數(shù)k稱為圖G的鄰點可區(qū)別全色數(shù)，記為x"a(G).關(guān)于鄰點可區(qū)別全染色，張忠輔等人提出以下猜想:階數(shù)至少是2的任意圖G有x"a(G)≤△(G)+3.我們將應(yīng)用代數(shù)工具“組合零點定理”研究圖的結(jié)構(gòu)，從而得出對于△(G)≥8的特殊平面圖G，以上猜想成立.
　　為了詳細清晰地闡述本文的主要結(jié)果，我們將論文分為五章.
　　第一章首先介紹圖論中相關(guān)的基本術(shù)語和定義，然后詳細敘述所要研究的圖類的基本

12、結(jié)構(gòu)和染色問題的定義、猜想以及目前的發(fā)展狀況，最后列出本文的主要結(jié)論.
　　第二章主要討論平面圖的無圈列表染色.重點是局部調(diào)整某些頂點的顏色從而討論相應(yīng)問題的圖結(jié)構(gòu)，最后得出主要結(jié)論.我們證明了如果平面圖G不含5-圈和相鄰4-圈，并且G中的任意一個頂點v至多關(guān)聯(lián)一個j-圈，j∈{6，7}，則G是無圈5-可選的.另外，我們還證明了如果平面圖G既不含三角化的5-圈也不含四角化的k-圈，其中，k∈{4，5}，則G是無圈6-可選的.

13、>　　第三章主要研究1-平面圖的邊染色問題.通過觀察分析△-臨界圖的結(jié)構(gòu)特點，我們證明了以下兩個結(jié)論:如果1-平面圖G的最大度至少為8且圖G中的每個5-圈至多含一條弦，則G是第一類的;如果IC-平面圖G的最大度至少為7且圖G不含相鄰弦6-圈，則G是第一類的.
　　第四章主要研究平面圖和l-平面圖的正常全染色、(p，1)-全染色以及鄰點可區(qū)別全染色.首先，對于正常全染色，通過分析1-平面圖的結(jié)構(gòu)特點，我們證明了以下結(jié)論:△(G)≥9

14、且g(G)≥4的1-平面圖G滿足x"(G)≤△(G)+2;△(G)≥12且g(G)≥5的1-平面圖G滿足x"(G)≤△(G)+1.其次，對于(p,1)-全染色問題，p＞2，我們證明了△(G)≥4p+4的平面圖G和△(G)≥6p+3且不含相鄰三角形的1-平面圖G的(p，1)-全色數(shù)均至多為△(G)+2p-2.最后，對于鄰點可區(qū)別全染色，我們證明了△(G)≥8且不含相鄰4-圈的平面圖G滿足x"a(G)≤△(G)+3.
　　第五章主要提