無(wú)指定構(gòu)型平面圖的選色與不完全選色性.pdf

1、圖G的選色數(shù),記為x<,l>(G),定義為最小的自然數(shù)k,使得滿足:對(duì)任一頂點(diǎn)給定k種顏色的列表,且染色時(shí)每個(gè)頂點(diǎn)的顏色只能從自身的顏色列表中選擇時(shí),總存在圖G頂點(diǎn)的一個(gè)正常著色.在第二章,論文證明了每個(gè)圍長(zhǎng)至少為4且不含(i)5-圈和6-圈或(ii)7-圈和8-圈或(iii)8-圈和9-圈的平面圖是3-可選色的.同時(shí)還證明了每個(gè)圍長(zhǎng)至少為4且不含6-圈,7-圈和9-圈的平面圖是3-可選色的.我們還討論了不完全選色的相關(guān)問(wèn)題.若對(duì)任一頂

2、點(diǎn)給定k種顏色的列表,染色時(shí)每個(gè)頂點(diǎn)的顏色只能從自身的顏色列表中選擇且每個(gè)頂點(diǎn)至多有d個(gè)鄰點(diǎn)染相同的顏色,總存在圖G的一個(gè)頂點(diǎn)的正常著色,則圖G稱為(k,d)<'*>-可選色的.在第三章,論文給出了關(guān)于輪胎圖的一個(gè)結(jié)構(gòu)性的定理,此定理加強(qiáng)了Borodin在[13]中的關(guān)于平面圖的類似結(jié)論.運(yùn)用此定理,證明了每個(gè)沒(méi)有相鄰三角形的輪胎圖是(4,1)<'*>-可選色的.論文還給出了尋找這樣一種著色的線性時(shí)間的算法.此外,論文還證明了每個(gè)無(wú)4-