在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 是屬於第二類。
| Identifer | oai:union.ndltd.org:CHENGCHI/B2002005098 |
| Creators | 粱志平, LIANG,ZHI-PING |
| Publisher | 國立政治大學 |
| Source Sets | National Chengchi University Libraries |
| Language | 中文 |
| Detected Language | Unknown |
| Type | text |
| Rights | Copyright © nccu library on behalf of the copyright holders |
Page generated in 0.002 seconds