圖型有2n+1個點且最大秩為2n-1的全著色問題

Abstract

圖的全著色是指將一個圖的點與邊著色，而滿足相連的兩點著不同顏色，且相鄰的點 與邊，和相連的兩邊也著不同顏色。圖G 的全著色數Xt(G) 是圖的全著色所需最少的 顏色數。考慮圖G 是個簡單圖，而G 的最大秩為△(G) ，從定義上可以知道：全著色 數不小於最大秩加一。Behzad和Vizing分別提出下列之推測： 全著色推測(TCC) 對任意簡單圖，全著色數不大於量大秩加二。 如果全著色推測(TCC) 成立，則我們可將圖分為兩型，當全著色數等於最大秩加一時 稱為第一型，當全著色數等於最大秩加二時稱為第二型。 在這篇論文中我們討論有關圖型有2n+1個點且最大秩為2n-1的全著色問題。我們能夠 決定當圖型的補圖是某些不相交星圖的聯集時，這種圖的類型。另外我們也討論一些 有2n+1個點且最大秩為2n-1的特殊形式關鍵圖。