平面圖和1-平面圖的若干染色問(wèn)題.pdf

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

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

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

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

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

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

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

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

9、-平面圖在圍長(zhǎng)的限制條件下的全色數(shù)的上界.
　　圖G的k-(p，1)-全染色是從V(G)∪ E(G)到顏色集合{0，1，…，k}的映射φ，使得圖G中相鄰或相關(guān)聯(lián)的元素滿足以下條件:當(dāng)uv∈E(G)時(shí)，|φ(u)-φ(v)|≥1;當(dāng)邊e1和邊e2相鄰時(shí)，|φ(e1)-φ(e2)|≥1;當(dāng)頂點(diǎn)u和邊e關(guān)聯(lián)時(shí)，|φ(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}.通過(guò)分析結(jié)構(gòu)性質(zhì)，我們得到最大度至少為4p+4的平面圖和最大度至少為6p+3的特殊1-平面圖的(p，1)-全色數(shù)的上界.
　　在圖G的一個(gè)正常k-全染色φ中，令Cφ(v)表示頂點(diǎn)v的顏色及與其關(guān)聯(lián)的邊的顏色集合.如果圖G中的任意一條邊uv滿足Cφ(u)≠Cφ(v)，則稱這個(gè)正常k-全染色φ為鄰點(diǎn)可區(qū)別k-全染色.使

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

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

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

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