1 |
完全r分圖及完全分裂圖之邊的塗色問題粱志平, LIANG,ZHI-PING Unknown Date (has links)
在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>m2+m3 二
個條件下, 則H 就是屬於第一類。又當m1=m2=m3=m4––1 時, 則H 是屬於第二類
。
最後, 對於完全分裂圖, 本篇論文是利用完全圖的塗色方法加以技巧化, 也是利用了
一個邊對應到顏色的函數證明的。所得到的結果是對於一個完全分裂圖S(=K(mln
),只要m+n為偶數或m 3n–5 時, 則S 就是屬於第一類。又當m+n是奇數和 m>
(n–1) 時, 則S 是屬於第二類。
|
Page generated in 0.0148 seconds