圖的全著色

Abstract

圖的全著色是指將一個圖的點與邊著色，而滿足相連的兩點著不同顏色，且相鄰點與 邊、兩邊也著不同顏色。圖Ｇ的全著色數 χt(Ｇ)是圖的全著色所需最少的顏色數。 考慮圖Ｇ是個簡單圖，而Ｇ的最大秩為 △(G)。從定義上可得知： χt(Ｇ)≧△(Ｇ)+1。Behzad 和 Vizing 獨立地提出下列推測： 全著色推測(TCC) 對任意簡單圖Ｇ，都可得到 χt(Ｇ)≦△(Ｇ)+2。 如果TCC 成立，則我們可將圖分為兩型，如果 χt(Ｇ)=△(Ｇ)+1 我們稱Ｇ為第一型， 否則稱Ｇ為第二型。而這種分類方式和邊著色對圖的分類相類似。 在本論文中，我們得到下列結果： ぇＯtt是第二型的充要條件為 t=2或t 為偶數且r 是奇數。 え圖G 的點數是2n，而最大秩為 2n-2 是第二型的充要條件是Ｇ的補圖為不相交的 1 ぉ分離圖滿足 TCC，而且當分離圖的最大秩是偶數時為第一型。