圖的強邊著色和列表強邊著色.pdf

1、本學位論文主要考慮圖的染色問題.圖的染色理論具有重要的理論意義和實際意義，是圖論研究的重要內容之一.所謂圖著色是指對圖中的頂點、邊等元素按照一定的規(guī)則進行分類.對象不同或規(guī)則不同，便有各式各樣的著色，隨著染色理論的發(fā)展又出現(xiàn)了許多新的染色.在現(xiàn)實生活中許多領域都會涉及到各種各樣的圖的染色問題，如點可區(qū)別染色、鄰強邊染色等.該問題被國內外學者廣泛研究和推廣.
　　 在圖的頂點染色和邊染色問題中，我們要求任意兩個相鄰頂點或相鄰邊所著

2、顏色不相同，如果距離為二的頂點或距離為二的邊所著顏色也不相同，我們就得到圖的距離二著色或稱強邊著色.圖的距離二著色實際上就是原圖的平方圖的頂點著色，我們對每條邊任意給一個顏色列表，如果邊的強邊著色均能在其列表中找到顏色，我們稱這種著色為列表強邊著色.近二十年來，關于圖的強邊著色問題的研究不斷涌現(xiàn).列表強邊著色問題的研究進一步拓廣了著色理論的實際應用范圍.
　　 本文主要研究的是圖的強邊著色和列表強邊著色問題.首先研究圖的列表強邊

3、著色.朱在文[11]中得到結論。
　　 若△(G)≤3且δ(G)≤2，則sx(G)≤10.
　　 若G為3正則圖，當g(G)=3時，sx(G)≤10.
　　 若G為3正則圖，當g(G)≥4時，sx(G)≤l1.
　　 本文將證明除一個僅7個頂點的特殊圖Ho外，對圖G的任一條邊xy，如果d(x)+d（y）≤5，則當二度點相鄰時，有sx1(G) 6；當二度點不相鄰時，有sx(G)≤ 7.該結果推進了列表強邊色