圖的鄰強(qiáng)邊染色.pdf

1、圖的鄰強(qiáng)邊染色問(wèn)題在計(jì)算機(jī)，網(wǎng)絡(luò)等領(lǐng)域都有廣泛的應(yīng)用.本學(xué)位論文討論的是圖的鄰強(qiáng)邊染色.用x'as(G)表示圖的鄰強(qiáng)邊色數(shù).關(guān)于圖的鄰強(qiáng)邊染色，張忠輔等人提出猜測(cè)：對(duì)于｜V(G)｜≥3的簡(jiǎn)單連通圖G，且G≠C5，則xas(G)≤△(G)+2.但是目前只知道一些特殊圖如樹(shù)，圈，完全二部圖，完全圖，Halin圖，唯圈圖等等的鄰強(qiáng)邊色數(shù)及一些上界. 在第二章中我們考慮了一般Mycielski圖的鄰邊強(qiáng)染色的問(wèn)題.給出具體的5-鄰強(qiáng)邊染

2、色來(lái)證明了圈的一般Mycielski圖的鄰強(qiáng)邊色數(shù)為5；還證明了若連通圖G(V,E)滿足x'as(G)≤△(G)+2，則x'as(Mn(G))≤△(Mn(G))+2.在第三章中利用最大度為4，圍長(zhǎng)大于6的平面圖的全色數(shù)為5的這個(gè)性質(zhì)，證明了最大度為4且圍長(zhǎng)至少為8的連通平面圖G(V,E)滿足猜想.研究了最大度為4的圖的鄰強(qiáng)邊染色的問(wèn)題得到了最大度為4的連通圖G(V,E)，有x'as(G)≤8. 在第四章中我們利用引理：若圖G滿足