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, The NP-completeness of edge-coloring, SIAM Journal on Computing, 1981, 10: 718–720.
- Sanders, Daniel P.; Zhao, Yue, Planar graphs of maximum degree seven are class I, Journal of Combinatorial Theory, Series B, 2001, 83 (2): 201–212.
- Vizing, V. G., Critical graphs with given chromatic class, Metody Diskret. Analiz., 1965, 5: 9–17. (In Russian.)