Vizing定理
定理陳述
Vizing定理:任意(簡單, 無向)圖 G 的邊著色數 (edge chromatic number, χ′(G)) 等於 Δ(G) 或 Δ(G) + 1,其中 Δ(G) 指圖 G 中最大的度。
分類法
由Vizing定理可知χ′(G)=Δ(G) 或 Δ(G) + 1。若為前者,稱G為第一類圖(Class 1),否則稱為第二類圖 (Class 2)。雖然只有兩類,但Holyer (1981)證明了,確定任意圖屬於哪一類是一個NP完全問題。
不過,對於特定類型的圖也有部分的解答。比如對於簡單平面圖,Vizing (1965)自己證明了,如果Δ(G)≥8 則是第一類的,但對於Δ(G)=2,3,4,5 的情況則有第二類圖存在:把正多面體的其中一邊截成兩條,即可得到 Δ(G)=3,4,5 的平面圖,他們是第二類的;而任何長度是奇數的圈(比如三角形)就是 Δ(G)=2 的第二類圖。對於剩下的兩種情況,Vizing提出了猜想:
- 平面圖Vizing猜想:
※任何簡單平面圖如果 Δ(G)≥6 (或7),則是第一類的。(Vizing 1965)
在 Δ(G)≥7 的情形,Sanders & Zhao (2001) 給出了肯定的結果。因此只剩下 Δ(G)≥6 的情形尚待解決。
不過一般來講,"大多數"的圖都是第一類的。
相关
參考資料
- Planet math
- Weisstein, Eric W. "Vizing's Theorem." From MathWorld--A Wolfram Web Resource.
- Holyer, Ian, , SIAM Journal on Computing, 1981, 10: 718–720.
- Sanders, Daniel P.; Zhao, Yue, , Journal of Combinatorial Theory, Series B, 2001, 83 (2): 201–212.
- Vizing, V. G., , Metody Diskret. Analiz., 1965, 5: 9–17. (In Russian.)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.