Vizing定理

Vizing定理：任意(簡單, 無向)圖 G 的邊着色數 （edge chromatic number, χ′(G)） 等於 Δ(G) 或 Δ(G) + 1，其中 Δ(G) 指圖 G 中最大的度。 ^[1] 

由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） ^[1] 

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

不過一般來講，"大多數"的圖都是第一類的。

在圖論中，Vizing的猜想涉及圖的支配數與笛卡爾積之間的關係。 這個猜想首先由Vadim G. Vizing（1968）提出，並指出，如果γ（G）表示G支配集中的最小頂點數，則

Gravier＆Khelladi（1995）推測圖的張量積的支配數有一個相似的界。 然而，Klavžar＆Zmazek（1996）發現了一個反例。 自Vizing提出他的猜想以來，許多數學家對此進行了研究，部分結果描述如下。 有關這些結果的更詳細概述，請參見Brešar等。 ^[1] 

一個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以及連接圖和單個邊的根乘積組成。 ^[1] 

顯然，當G或H的支配數為1時，該猜想成立：因為，乘積包含其他因子的同構副本，支配該主因子至少需要

個頂點。

Vizing的猜想對於週期和控制數為2的圖也成立。

Clark＆Suen（2000）證明，對於所有G和H，乘積的支配數至少是猜想範圍的一半。 ^[1] 

Vizing（1968）觀察到

^[1] 

可以將滿足此邊界的支配集形成為G或H中一個支配集與另一圖中所有頂點的集合的笛卡爾積。