圖的點可區(qū)別染色、列表染色和線性染色.pdf

1、圖論的研究已經(jīng)有二百多年的歷史,最早關(guān)于圖論的文章是在1736年由Euler完成的,這篇文章解決了著名的哥尼斯堡七橋問題.自二十世紀(jì)六十年代以來,圖論得到了迅猛發(fā)展,關(guān)于圖論方面的結(jié)果大量涌現(xiàn).一百多年以來,四色猜想一直引領(lǐng)著圖論的發(fā)展,所以圖的染色理論在圖論研究中占有重要的地位.圖的染色理論在最優(yōu)化、計算機(jī)理論、網(wǎng)絡(luò)設(shè)計等方面都有著重要的應(yīng)用,例如在網(wǎng)絡(luò)中的數(shù)據(jù)傳輸、Hessians矩陣的計算等方面.本文旨在討論圖的幾類染色問題,如點

2、可區(qū)別邊染色、鄰點可區(qū)別邊染色、鄰點可區(qū)別全染色、列表邊染色、列表全染色和線性染色.
　　 本文所考慮的圖都是有限簡單圖,我們分別用 V(G)和E(G)表示圖G的頂點集和邊集.圖 G的正常k-全染色是指用k種顏色對V(G)∪ E(G)中的元素進(jìn)行染色,使得相鄰的或者相關(guān)聯(lián)的兩個元素染不同的顏色.使得圖G存在正常的k-全染色的最小正整數(shù)k稱為G的全色數(shù),記作 X"(G).類似地,如果我們只對圖G的頂點或者邊進(jìn)行染色,那么就可以分別

3、得到圖G的點色數(shù)X(G)和邊色數(shù) X'(G).
　　 接下來我們給出的三種染色都與非正規(guī)染色有關(guān).對于一個正常的邊染色,如果它滿足任何兩個不同的點所鄰接的邊染色集合不相同,那么就稱這個染色是點可區(qū)別的.一個圖G存在一個點可區(qū)別邊染色所需要的最小顏色數(shù)稱為該圖的vde-色數(shù),記作 X'vdG).一個 k-鄰點可區(qū)別邊染色或者 k-avd-染色是指圖的一個正常邊染色,它滿足任何一對相鄰的頂點都鄰接不相同的顏色集合.一個圖G存在一個a

4、vd-染色所需要的最小顏色數(shù)稱為圖 G的avd-色數(shù),記作Xa'(G).一個k-鄰點可區(qū)別全染色或者 k-adt-染色是指圖的一個正常全染色,它滿足任何一對相鄰的頂點鄰接的顏色集合均不同.一個圖G存在一個adt-染色所需要的最小顏色數(shù)稱為圖的adt-色數(shù),記作Xa"(G).本文給出了與這些染色有關(guān)的一些上界.本文討論的另一個問題是列表染色.如果對于圖G的每一條邊e,我們都給定一個顏色集合L(e),那么這個映射L就稱為圖G的一個邊安排.如

5、果圖G存在邊染色ψ使得對任意邊 e∈E(G),都有ψ(e)∈L(e),則稱圖G是L-邊可染的,或者稱ψ是圖G的一個L-邊染色.對于圖G的任意一個滿足條件｜L(e)｜≥k的邊安排L,其中e∈E(G)為G的任意一條邊,如果G都是L-邊可選擇的,那么就稱圖G是k-邊可選擇的.使圖G是k-邊可選擇的最小正整數(shù)k稱為圖G的列表邊色數(shù),記作Xl'(G).類似地,我們可以給出圖G的列表色數(shù)Xl(G)和列表全色數(shù) Xl"(G),它們分別是把上述邊染色換

6、為對圖G的頂點或者頂點和邊進(jìn)行染色.從上述定義中我們馬上可以得到下列關(guān)系:Xl'(G)≥X’(G)≥△,Xl"(G)≥X"(G)≥△+1.本文主要討論平面圖的列表染色.對于圖G的一個正常k-染色,如果它滿足任意兩個顏色集合的導(dǎo)出子圖都是點不交的路的并,那么就稱該染色是圖G的一個線性k-染色.使得圖G存在一個線性k-染色的最小正整數(shù)k稱為圖G的線性色數(shù),記作lc(G).我們的目標(biāo)是找到圖G線性色數(shù)的一個較小的上界.
　　 本文主要

7、考慮圖的幾類染色問題.具體地說,我們主要討論圖的點可區(qū)別邊染色、鄰點可區(qū)別邊染色、鄰點可區(qū)別全染色、列表邊染色、列表全染色和線性染色.本文分六章進(jìn)行討論.
　　 在第一章,我們給出一個相對完整的簡介:首先,我們介紹一些圖論中的基本概念和定義；然后,我們給出本文所討論的染色的定義和歷史；最后我們給出了本文的主要結(jié)論.
　　 在第二章,我們討論了圖的點可區(qū)別邊染色.我們改進(jìn)了 Bazgan等人在文章[13]證明的一個結(jié)論,把

8、其中的條件δ(G)>n/3放寬到了σ2(G)≥2n/3.我們證明的基本方法是先給圖 G一個半-vde-染色,然后再用額外的幾種顏色把它擴(kuò)展到整個圖G上去.
　　 在第三章,我們討論了圖的鄰點可區(qū)別邊染色.首先,我們給出了周長不超過4的圖的avd-色數(shù)的一個上界.然后我們考慮了幾類3-可染的圖,并給出了它們 avd-色數(shù)的上界.
　　 在第四章,我們討論了周長不超過4的圖的adt-色數(shù),并給出了它的一個上界.