圖的強(qiáng)邊著色和列表強(qiáng)邊著色.pdf

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

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

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