不含相鄰短圈的平面圖的全染色.pdf

1、本文考慮的圖均為有限、簡(jiǎn)單、無(wú)向圖。對(duì)于任意一個(gè)圖G，它的頂點(diǎn)集、邊集、面集、最小度和最大度分別用V（G）、E（G）、F（G）、δ（G）和△（G）來(lái)表示． 圖G的一個(gè)正常全k—染色是從V（G）∪E（G）到顏色集{1，2，3…k}的一個(gè)映射λ，它使得任意相鄰接或關(guān)聯(lián)的元素x，y∈V（G）∪E（G），都有λ（x）≠λ（y）．如果圖G有一個(gè)正常全k—染色，則稱圖G足全k—可染色的，定義XT（G）=min{k|G是全k—可染色的}為圖G

2、的全色數(shù)。顯然，對(duì)任意圖G，都有XT（G）≥△（G）+1．Behzad和Vizing在1965年分別獨(dú)立提出了下面猜想： 全染色猜想（TCC）：任意圖G，都滿足χT（G）≤△（G）+2． 對(duì)于一般的圖，人們已經(jīng)證明當(dāng)△（G）≤5時(shí)，TCC猜想成立．對(duì)于平面圖，已經(jīng)證明當(dāng)△（G）≥7時(shí)，TCC猜想成立．從而全染色猜想對(duì)平面圖只?！鳎℅）=6的情形尚未證明。對(duì)任意圖G，如果XT（G）=△（G）+1，則稱G是第Ⅰ類圖；如果XT