本文選題：無圈列表染色 + 邊染色��； 參考：《山東大學(xué)》2017年博士論文

【摘要】：圖的染色問題是圖論領(lǐng)域中一個(gè)經(jīng)典而且比較活躍的分支.圖的染色問題已由傳統(tǒng)的邊染色、點(diǎn)染色和全染色發(fā)展為種類繁多的新型染色問題,每種染色都有著各自重要的理論價(jià)值和適當(dāng)?shù)膽?yīng)用背景.這些新型染色問題在算法設(shè)計(jì)、時(shí)間排序問題以及資源分配問題中有著廣泛的應(yīng)用,這不僅產(chǎn)生了許多有趣的未解決問題,而且也促使研究方法不斷創(chuàng)新,從而極大地豐富了圖的染色理論.本文主要研究平面圖和1-平面圖的無圈列表(點(diǎn))染色、正常邊染色、正常全染色、(p,1)-全染色以及鄰點(diǎn)可區(qū)別全染色問題.除非特殊說明,約定本文中所涉及到的圖均為有限、無向、簡(jiǎn)單且非空的圖.給定圖G,用V(G),E(G),△(G)分別表示圖G的頂點(diǎn)集,邊集和最大度.v(G)=|V(G)|和e(G)= |E(G)|分別表示G的階數(shù)和邊數(shù).圖G的圍長是G中最短圈的長度,記為g(G).如果一個(gè)圈除了自身以外它相鄰一個(gè)3-圈,則稱此圈為三角化的;如果一個(gè)圈除了自身以外它相鄰一個(gè)4-圈,則稱此圈為四角化的.平面圖是指能夠嵌入到平面上使得其任意兩條邊僅在端點(diǎn)處相交的圖,這樣的嵌入稱為平面嵌入,該平面嵌入稱為平圖.1-平面圖G是指G能夠嵌入到平面上使得G的任意一條邊最多被交叉一次.1-平面圖G按照上述條件的一種畫法稱為G的一種1-平面嵌入,此1-平面嵌入稱為1-平圖.所以1-平圖中的每個(gè)交叉點(diǎn)ω都是由兩條邊相交所得,從而每個(gè)交叉點(diǎn)ω都對(duì)應(yīng)著兩條相交邊,同時(shí)也對(duì)應(yīng)著由這兩條相交邊的四個(gè)端點(diǎn)組成的集合ψ(ω).如果1-平面圖的一個(gè)1-平面嵌入中任意兩個(gè)交叉點(diǎn)ω和ω'滿足ψ(ω)nψ(ω')=(?),則稱此1-平面圖為IC-平面圖.給定圖G =(V(G),E(G)),它的正常k-點(diǎn)染色是指一個(gè)映射φ:V(G)→{1,2,…,k},使得圖G中任意兩個(gè)相鄰的頂點(diǎn)u和滿足φ(u)≠ φ(v).使得G具有正常k-點(diǎn)染色的最小正整數(shù)k稱為G的點(diǎn)色數(shù),記為χ(G).在圖G的一個(gè)正常點(diǎn)染色φ中,如果G中的每個(gè)圈上至少有三種顏色,則稱φ為圖G的無圈染色.如果給圖G的每個(gè)頂點(diǎn)v ∈ V(G)都分配一個(gè)顏色集合L(v),則稱L={L(v:v V ∈ }為G的一個(gè)點(diǎn)列表.給定點(diǎn)列表L,如果G中存在無圈染色φ使得每個(gè)頂點(diǎn)v的顏色滿足φ(v)∈L(v)則稱圖G是無圈L-可染的.如果對(duì)任意點(diǎn)列表L,圖G是無圈L-可染的,其中對(duì)任意點(diǎn)v ∈ V(G)有|L(v)|≥ k,則稱圖G是無圈k-可選的.使得圖G是無圈k-可選的最小正整數(shù)k稱為G的無圈列表色數(shù),記為χal(G).Borodin等人猜想:每個(gè)平面圖都是無圈5-可選的.我們主要討論具有相鄰3-圈的平面圖是無圈5-可選或者無圈6-可選的充分條件.圖G的一個(gè)正常k-邊染色是一個(gè)映射φ:E(G)→ {1,2,…,k},使得任意兩條相鄰的邊x,y ∈ E(G)滿足φ(x)≠φ(y).使得G具有正常k-邊染色的最小正整數(shù)k稱為圖G的邊色數(shù),記為χ'(G).著名Vizing定理證明每個(gè)簡(jiǎn)單圖G的邊色數(shù)χ'(G)要么等于最大度△(G)要么等于△(G)+1。這個(gè)定理將所有的圖分成了兩類:第一類圖滿足關(guān)系式χ'(G= △(G),第二類圖滿足關(guān)系式χ'(G)= △(G)+ 1.如果連通圖G是第二類圖,并且對(duì)G中的任意邊e有不等式χ'(G-e)χ'(G)成立,則稱G是臨界圖.如果G是最大度為△的臨界圖,則稱G為△-臨界圖.張欣和吳建良證明了每個(gè)最大度至少為10的1-平面圖是第一類的.同時(shí),張欣構(gòu)造了最大度為6或7的第二類的1-平面圖,隨后張欣和劉桂真提出了猜想:每個(gè)最大度至少為8的1-平面圖都是第一類的.我們證明了最大度至少為8的1-平面圖和最大度至少為7的IC-平面圖在限制弦圈的條件下是第一類的.圖G的一個(gè)正常l-全染色是一個(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ù),記為χ"(G).Behzad與Vizing分別獨(dú)立地提出了著名的全染色猜想:任意簡(jiǎn)單圖G滿足≤ △(G)+ 2.根據(jù)1-平面圖的結(jié)構(gòu)特點(diǎn)和附加結(jié)構(gòu)特征,我們分別確定了最大度至少為9和最大度至少為12的1-平面圖在圍長的限制條件下的全色數(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ù),記為λpT(G).Havet和Yu提出了(p,1)-全染色猜想:任何圖G滿足λpT(G)≤ min{△(G)+ 2p-1,2△(G)+ p-1}.通過分析結(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-全染色.使得G具有鄰點(diǎn)可區(qū)別k-全染色的最小正整數(shù)k稱為圖G的鄰點(diǎn)可區(qū)別全色數(shù),記為χa"(G).關(guān)于鄰點(diǎn)可區(qū)別全染色,張忠輔等人提出以下猜想:階數(shù)至少是2的任意圖G有χa"(G)≤ △(G)+3.我們將應(yīng)用代數(shù)工具"組合零點(diǎn)定理"研究圖的結(jié)構(gòu),從而得出對(duì)于△(G)≥ 8的特殊平面圖G,以上猜想成立.為了詳細(xì)清晰地闡述本文的主要結(jié)果,我們將論文分為五章.第一章首先介紹圖論中相關(guān)的基本術(shù)語和定義,然后詳細(xì)敘述所要研究的圖類的基本結(jié)構(gòu)和染色問題的定義、猜想以及目前的發(fā)展?fàn)顩r,最后列出本文的主要結(jié)論.第二章主要討論平面圖的無圈列表染色.重點(diǎn)是局部調(diào)整某些頂點(diǎn)的顏色從而討論相應(yīng)問題的圖結(jié)構(gòu),最后得出主要結(jié)論.我們證明了如果平面圖G不含5-圈和相鄰4-圈,并且G中的任意一個(gè)頂點(diǎn)v至多關(guān)聯(lián)一個(gè)j-圈,j ∈ {6,7},則G是無圈5-可選的.另外,我們還證明了如果平面圖G既不含三角化的5-圈也不含四角化的k-圈,其中,k∈ {4,5},則G是無圈6-可選的.第三章主要研究1-平面圖的邊染色問題.通過觀察分析△-臨界圖的結(jié)構(gòu)特點(diǎn),我們證明了以下兩個(gè)結(jié)論:如果1-平面圖G的最大度至少為8且圖G中的每個(gè)5-圈至多含一條弦,則G是第一類的;如果IC-平面圖G的最大度至少為7且圖G不含相鄰弦6-圈,則G是第一類的.第四章主要研究平面圖和1-平面圖的正常全染色、(p,1)-全染色以及鄰點(diǎn)可區(qū)別全染色.首先,對(duì)于正常全染色,通過分析1-平面圖的結(jié)構(gòu)特點(diǎn),我們證明了以下結(jié)論:△(G)≥ 9 且 g(G)≥ 4 的 1-平面圖 G 滿足 χ"(G)≤ △(G)+ 2;△(G)≥ 12且g(G)≥ 5的1-平面圖G滿足χ"(G)≤ △(G)+1.其次,對(duì)于(p,1)-全染色問題,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滿足χa"(G)≤ △(G)+3.第五章主要提出了現(xiàn)階段正在研究的問題,并指出今后研究工作中幾個(gè)可行的研究思路和方法.
[Abstract]:In this paper , we have shown that G can be embedded in the plane so that any two edges of G can be embedded in the plane so that any two edges of G can be embedded in the plane . Let G be an acyclic k - optional minimum positive integer k called G . If there is no circle in G , it is called 蠂 ' ( G ) . Let G have a minimum positive integer k of normal k - total coloring , called the total chromatic number of graph G . It is known as 蠂 " ( G ) . The best degree of G is equal to 鈮，

本文編號(hào)：1911930