在1964年, V.G.Vizing證明了: 假如一個圖G 的最大度數為ρ時, 則G 的著色數不是

ρ就是ρ＋1。那G 的著色數定義為X (G)。若X (G)=ρ時, 我們說G 是屬於第二類。

本篇論文主要研究的圖是完全3 分圖、完全四分圖及完全分裂圖。研究目的是希望找

出對於這三種圖在何種條件下是屬於第一類, 又在何種條件下是屬於第二類。

對於完全3 分配及完全4 分圖, 本篇論文是利用一個從邊對應到顏色的函數去證明的

。所得到的結果是，對一個完全3 分圖G （＝K ）, 只要m1≠m2和m3＜2m

1 二個條件下, 則G 就是屬於第一類。又當m1＝m2＝m3＝m, m是偶數時, 則G 是屬於

第二類。對於一個完全4 分圖H（＝K ）, 只要m1≠m3和m1＋m4＞ｍ2＋m3 二

個條件下, 則H 就是屬於第一類。又當m1＝m2＝m3＝m4––1 時, 則H 是屬於第二類

。

最後, 對於完全分裂圖, 本篇論文是利用完全圖的塗色方法加以技巧化, 也是利用了

一個邊對應到顏色的函數證明的。所得到的結果是對於一個完全分裂圖S（＝K（mln

），只要m＋n為偶數或m 3n–5 時, 則S 就是屬於第一類。又當m＋n是奇數和 m＞

（n–1） 時, 則S 是屬於第二類。