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提出了猜想：

※任何简单平面图如果 Δ(G)≥6 (或7)，则是第一类的。（Vizing 1965）

在 Δ(G)≥7 的情形，Sanders & Zhao (2001) 给出了肯定的结果。因此只剩下 Δ(G)≥6 的情形尚待解决。

在图论中，Vizing的猜想涉及图的支配数与笛卡尔积之间的关系。 这个猜想首先由Vadim G. Vizing（1968）提出，并指出，如果γ（G）表示G支配集中的最小顶点数，则

Gravier＆Khelladi（1995）推测图的张量积的支配数有一个相似的界。 然而，Klavžar＆Zmazek（1996）发现了一个反例。 自Vizing提出他的猜想以来，许多数学家对此进行了研究，部分结果描述如下。 有关这些结果的更详细概述，请参见Brešar等。

一个4回路-C4具有第二个支配地位：任何顶点仅支配自己及两个邻居，但是任何一对顶点支配整个图形。乘积是一个多维超立方体图；它有16个顶点，并且任何一个顶点只能控制自己和四个邻居，因此三个顶点只能控制16个顶点中的15个。因此，至少需要四个顶点来控制整个图形，该界限由Vizing的猜想给出。

乘积的支配数可能比Vizing猜想所给定的界限大得多。例如，对于星图K1,n，其支配数为1：可以在其中心使用单个顶点控制整个图。因此，对于由两个图的乘积形成的图，Vizing的猜想仅表明支配数应至少为1 ×1 =1。但是，此图的支配数实际上要高得多。它具有个顶点：由两个因数的叶子的乘积形成，2n由一个因数的叶子的乘积和另一个因数的中心点形成，剩下的一个顶点由两个因数的乘积形成。 G中的每个叶集乘积顶点正好控制n个叶顶点，因此需要n个叶集顶点才能控制所有叶顶点。但是，没有叶子中心顶点支配任何其他此类顶点，因此，即使在选择n个叶子中心顶点包含在支配集中之后，仍然存在n个以上未被控制的叶子中心顶点，这些顶点可以由单个中心支配-中心顶点。因此，该图的支配数为远高于Vizing给定的平凡边界。推测。

存在无穷系列的图积，正好满足Vizing猜想的范围。例如，如果G和H都是连通图，每个图至少具有四个顶点，并且总顶点数恰好是其支配数的两倍，则。具有此属性的图G和图H由四个顶点循环C4以及连接图和单个边的根乘积组成。

显然，当G或H的支配数为1时，该猜想成立：因为，乘积包含其他因子的同构副本，支配该主因子至少需要个顶点。

Vizing的猜想对于周期和控制数为2的图也成立。

Clark＆Suen（2000）证明，对于所有G和H，乘积的支配数至少是猜想范围的一半。

Vizing（1968）观察到

可以将满足此边界的支配集形成为G或H中一个支配集与另一图中所有顶点的集合的笛卡尔积。