Vizing定理

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 的情形尚待解决。

不过一般来讲,"大多数"的图都是第一类的。[来源请求]

相关

参考资料