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

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

2、表染色、均勻染色和一些其它類型的染色.其中在第一章，我們將先給出與本文有關的一些概念、符號和本學位論文的結構，同時也給出了與本文有關內容的研究背景、研究歷史和研究綜述. 在第二章，主要討論圖的邊染色，在圖的邊染色理論中。有一個眾所周知的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各自獨立地解決了△(G)=7時的Vizing猜測.至此，Vizing的平面圖猜測只在△(G)=6時尚未解決.我們在這一章主要討論△(G)=6的平面圖的分類問題.證明了：若平面圖G的最大度△=6，不含有弦4-圈，則G是第一類的；若G是最

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

5、義中的條件弱化，提出了鄰強邊染色概念，并提出如下猜想：對于｜V(G)｜≥3的連通簡單圖G，G≠C5有X'a(G)≤△(G)+2.就目前而言，有關這方面的結論很少，只知道一些特殊的圖類如：樹、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-頂點可染的，則對每個不小于k的整數(shù)l，圖G也是l-頂點可染的.但對于一個k-均勻可染的圖G和不小于七的整數(shù)l，圖G未必是l-均勻可染的. 在第四章，我們主要圍繞Meyer于1973年提出

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