本文關(guān)鍵詞： 全染色 列表染色 鄰和可區(qū)別的全染色 列表線性蔭度　出處：《山東大學(xué)》2017年博士論文　論文類型：學(xué)位論文

【摘要】：圖論最早源于著名的哥尼斯堡七橋問題,已有兩百多年的發(fā)展史.圖的染色理論起源于四色問題,是圖論研究中最重要的課題之一.在自然科學(xué)、社會(huì)科學(xué)領(lǐng)域都有重要的應(yīng)用.在本論文中,我們研究了圖的全染色、列表染色、鄰和可區(qū)別全染色和列表線性蔭度的問題.若無特別明確指出,本文所考慮的都是簡單的,無向的,有限的和非空的圖.令G =(V,E)是一個(gè)圖,對(duì)一個(gè)點(diǎn)v∈V(G),用NG(v)表示v在圖G中的鄰點(diǎn)集,dG(v)= |NG(v)|是點(diǎn)v的度數(shù).圖G的最大度和最小度分別用Δ(G)和δ(G)表示.為方便起見,令Δ = Δ(G)和δ = δ(G).圖G的kk-全染色是指用k種顏色(1,2,…,k)對(duì)V(G)∪E(G)中的元素進(jìn)行染色,使得相鄰的兩個(gè)元素或者相關(guān)聯(lián)的兩個(gè)元素染不同的顏色.圖G的所有k-全染色中的最小正整數(shù)k稱為G的全色數(shù),記為χ"(G).關(guān)于圖的全染色猜想(Total Coloring Conjecture):對(duì)任意圖 G,Δ + 1 ≤ χ"(G)≤Δ+ 2.這個(gè)猜想對(duì)于△ ≤ 5的一般圖都成立.隨著研究的不斷深入,研究者發(fā)現(xiàn)有很多圖的全色數(shù)不只滿足全染色猜想,還可以取到相應(yīng)的下界,也就是說χ"(G)= Δ + 1.就平面圖而言,對(duì)△ = 6的平面圖全染色猜想還未證明成立.而對(duì)△ ≥ 9的平面圖G,已經(jīng)證明了 χ"(G)= Δ + 1.對(duì)4≤Δ≤8的平面圖,也未找到不能(Δ+1)-全可染的例子.于是有了平面圖猜想:任意最大度至少為4的平面圖是(△ +1)-全可染的.本文在第二章證明了平面圖的全染色的三個(gè)相關(guān)結(jié)果:(1)對(duì)于△ ≥ 8的平面圖G,若任何兩個(gè)弦6-圈不相鄰或者任意6-圈至多只含一條弦,則χ"(G)= △ + 1;(2)對(duì)于△ ≥ 8的平面圖G,若任何7-圈至多含兩條弦,則χ"(G)= Δ + 1;(3)對(duì)于△ ≥ 7的平面圖G,若任何兩個(gè)弦5-圈不相交,則χ"(G)= △ + 1.一個(gè)映射L被稱為圖G的一個(gè)分配,如果對(duì)于每個(gè)點(diǎn)v ∈ V(G),都有一個(gè)列表L(v).如果G存在一種染色使得每個(gè)點(diǎn)從列表中得到顏色,并且每兩個(gè)相鄰的點(diǎn)顏色不同,我們稱G是L-點(diǎn)可染的.稱圖G是kk-點(diǎn)可選的,如果|L(v)| ≥ kk且G是點(diǎn)可染的,這里v是G中的任意一個(gè)點(diǎn).我們?cè)诘谌伦C明了平面圖G中3-圈或4-圈不同時(shí)與5-圈相鄰,G是4-可選的.如果對(duì)于圖G的任意一條邊e ∈E(G),我們給其一個(gè)顏色集合L(e),那么就稱L為G的一個(gè)邊列表.對(duì)于圖G的任意一個(gè)滿足條件|L(e)| ≥k的邊列表L,其中e ∈E(G)為G的任意一條邊,如果G都是L-邊可染的,那么就稱圖G是k-邊可選的.使圖G是kk-邊可選的最小正整數(shù)k稱為圖G的列表邊色數(shù),記作χ"(G).類似地,我們可以給出圖G的列表全色數(shù)χl"(G)的定義,即把上述邊染色換為對(duì)圖的頂點(diǎn)和邊進(jìn)行染色.在第三章我們證明了對(duì)于平面圖G,若最大度Δ(G)8,且4-圈與5-圈不相鄰,則χl'(G)= Δ,χl"(G)+ 1;若最大度Δ(G)≥ 6,且4-圈與5-圈不相鄰,則χl'(G)= Δ + 1,χl"(G)= Δ + 2.近年來,魔幻、反魔幻標(biāo)號(hào)、非正則強(qiáng)度等與"和(sum)"有關(guān)的染色與標(biāo)號(hào)問題引起了廣泛關(guān)注,其中比較著名的有1-2-3猜想和1-2猜想.本文的第四章給出圖的鄰和可區(qū)別全染色的定義,并給出相關(guān)問題的一些猜想和主要研究進(jìn)展.用f(v表示點(diǎn)v及所有與其關(guān)聯(lián)的邊的顏色的加和,如果對(duì)任意的邊uv,有f(u)≠ f(v)，則稱這樣的kk-全染色為圖G的k-鄰和可區(qū)別全染色.k的最小值稱為圖G的鄰和可區(qū)別全色數(shù),定義為χ∑"(G).Pilsniak和Wozniak猜想對(duì)至少兩個(gè)頂點(diǎn)的圖G,χ∑" ≤ △(G)+ 3.目前這個(gè)猜想已經(jīng)證明對(duì)于完全圖,圈,二部圖,立方圖,系列平行圖和△ ≥ 14的平面圖都成立.我們證明了對(duì)于可嵌入到歐拉示性數(shù)非負(fù)曲面的圖來說,χ∑"(G)≤ max{Δ(G)+ 2,16}.最后,本文還討論了平面圖的列表線性蔭度.一個(gè)圖G的線性蔭度是指把圖G中的邊集剖分成線性森林的最小數(shù)目,記為la(G).Akiyama等人猜想kα(G)≤[Δ(G)+1/2]對(duì)每個(gè)正則圖G都成立.顯然,對(duì)于每個(gè)圖G都有l(wèi)a(G)≥[Δ(G)/2],對(duì)于每個(gè)正則圖G都有l(wèi)a(G)≥[Δ(G)+1/2],因此,Akiyama等人的猜想等價(jià)于如下猜想,即線性蔭度猜想:設(shè)G是一個(gè)簡單圖,則[Δ(G)/2]kα(G)「Δ(G)+1/2].如果對(duì)于圖G的任意一條邊e ∈ E(G),我們給其一個(gè)顏色集合L(e)(?)N,那么就稱L為G的一個(gè)邊列表,其中N是一個(gè)正整數(shù)集合.如果G存在一個(gè)正常的邊染色φ(e)使得對(duì)每條邊e有φ(e)∈ L(e)且對(duì)任意的i ∈ Cφ有(V(G),φ-1(i),其中Gφ = {φ(e)|e ∈E(G)}.那么我們說G是線性L-可染的且φ是G的線性的L-染色.我們說G是線性k-可選的如果G是線性L-可染的且對(duì)于所有邊e的每個(gè)列表分配L滿足|L(e)|≥ k.一個(gè)圖G的列表線性蔭度lalist(G)定義為G是線性kk-列表可染的最小值k.顯然la(G)≤lalist(G).本文的第五章,我們證明了如果G是一個(gè)平面圖且G中7-圈至多含兩條弦,那么若Δ(G)≥ 6,則G是線性[Δ+1/2]-可選的,若Δ(G)11,則G是線性[[Δ/2]-可選的.在本文的第六章,我們將對(duì)全文進(jìn)行總結(jié),并提出在圖的染色問題中一些今后可繼續(xù)研究的課題.
[Abstract]:鍥捐鏈，

本文編號(hào)：1556136