關(guān)于圖染色中若干參數(shù)的研究.pdf

1、本學(xué)位論文主要考慮圖的染色問題.圖的染色理論是圖論研究的重要內(nèi)容之一.隨著實(shí)際問題的需要，各種各樣的圖染色問題已被國內(nèi)外的學(xué)者廣泛研究和推廣，如均勻染色、點(diǎn)(邊)可區(qū)別染色、鄰強(qiáng)邊染色、列表染色等。由于確定一個圖的點(diǎn)(邊)色數(shù)是NP-完全問題，因此，確定圖的這些特殊染色同樣是NP-完全的.目前對這些問題的討論基本上限制在一些具有一定條件下的圖的這些特殊染色. 本學(xué)位論文共分五章，主要考慮無短圈平面圖的邊染色、點(diǎn)可區(qū)別染色、均勻列

2、表染色、均勻染色和一些其它類型的染色.其中在第一章，我們將先給出與本文有關(guān)的一些概念、符號和本學(xué)位論文的結(jié)構(gòu)，同時也給出了與本文有關(guān)內(nèi)容的研究背景、研究歷史和研究綜述. 在第二章，主要討論圖的邊染色，在圖的邊染色理論中。有一個眾所周知的Vizing定理：對每個簡單圖G，有△(G)≤x'(G)≤△(G)+1.根據(jù)這一定理，將簡單圖劃分為兩類：滿足X'(G)=△(G)的圖稱為第一類圖；滿足x'(G)=△(G)+1的圖稱為第二類圖.在

3、過去的若干年中，已經(jīng)確定了一系列的第一類或第二類圖.Vizing證明了每個△(G)≥8的平面圖是第一類的.同時猜測：每一個6 ≤△(G)≤ 7的簡單平面圖都是第一類的.Sanders與Zhao以及Zhang各自獨(dú)立地解決了△(G)=7時的Vizing猜測.至此，Vizing的平面圖猜測只在△(G)=6時尚未解決.我們在這一章主要討論△(G)=6的平面圖的分類問題.證明了：若平面圖G的最大度△=6，不含有弦4-圈，則G是第一類的；若G是最

4、大度△=6且不含有弦5-圈和有弦6-圈的平面圖，則G是第一類圖；每個△(G)=6且不含6-圈的平面圖也是第一類的.同時討論了一類平面圖的邊-面染色. 在第三章，我們探討了點(diǎn)可區(qū)別染色問題.最初對這個問題的考慮來自于不規(guī)則網(wǎng)絡(luò).1997年，Burris和Schelp將這個問題限制到染色問題上，提出了點(diǎn)可區(qū)別邊染色.同時，J.Cerry,M.Hornak和R.Sotak也獨(dú)立提出了相似的概念.張忠輔等人于2000年將點(diǎn)可區(qū)別邊染色定

5、義中的條件弱化，提出了鄰強(qiáng)邊染色概念，并提出如下猜想：對于｜V(G)｜≥3的連通簡單圖G，G≠C5有X'a(G)≤△(G)+2.就目前而言，有關(guān)這方面的結(jié)論很少，只知道一些特殊的圖類如：樹、Halin圖、最大度為4的外平面圖、二部圖和最大度為3的圖滿足該猜想.在本章，我們主要圍繞這一猜想展開討論.證明了：若圖G沒有孤立邊，g(G)≥6，則X'a(G)≤△(G)+2：若圖G是階至少為5，△(G)=4并且沒有孤立邊的圖，則有X'a(G)≤8

6、. 圖的均勻染色研究歷史相對較長，早在1964年，Erdos就猜測：任何一個圖G和整數(shù)k≥△(G)，G有一個(k+1)-均勻染色.這一猜測于1970年被Hajnal和Szemerédi所證明.均勻染色與經(jīng)典染色存在較大差異，眾所周知，若圖G是k-頂點(diǎn)可染的，則對每個不小于k的整數(shù)l，圖G也是l-頂點(diǎn)可染的.但對于一個k-均勻可染的圖G和不小于七的整數(shù)l，圖G未必是l-均勻可染的. 在第四章，我們主要圍繞Meyer于1973年提出

7、的猜想：如果G是不為完全圖和奇圈的連通圖，則Xe(G)≤△(G)和2003年，Kostochka,Pelsmajer和West提出的猜想：對于圖G，當(dāng)k≥△(G)+1時，G是k-均勻可選擇的展開研究，討論了不含4-圈和7-圈的平面圖，不含4-圈和6-圈的平面圖，不含5-圈和6-圈的平面圖和不含3-圈的平面圖的均勻染色以及均勻列表染色. 在第五章，我們討論了圖的色可選擇性問題.一個圖若滿足色數(shù)與選擇數(shù)相等，就稱圖G是色可選擇的.G