基本介紹
- 中文名:哈德威格猜想
- 外文名:Hadwiger's conjecture
- 所屬學科:數學
- 所屬問題:組合學(圖與超圖)
- 簡介:關於圖的著色的一個著名猜想
- 提出者:哈德威格(H.Hadwiger)
基本介紹,哈德威格猜想的相關證明,
基本介紹
哈德威格猜想(Hadwiger 1943,1958):對所有的正整數k,每個滿足
的圖一定含有Kk作為幼圖。

當
時,哈德威格猜想很容易被驗證。Hadwiger和Dirac證明了當k=4時,猜想成立。Wagner和Robertson,Seymour和Thomas分別證明了當k=5和k=6時,猜想與四色定理等價。對
,猜想看起來是圖論中最難解決的問題之一。


Hajós曾經考慮過另一個更強的猜想:每個
的圖一定含有一個Kk的細分。當k≤4時,Hajós這個猜想已被驗證。對每個k≥7, Catlin(1979)找到了Hajós猜想的反例。從而Hajós的這個猜想只在k=5和k=6時仍未解決。

受到Kuratowski定理的啟發,Chartrand,Geller和Hedetniemi猜想每個滿足
的圖或者含有一個Kk的細分,或者含有一個
的細分。但Hanson和Toff(1994),可能還有Woodall(1990),注意到Catlin的關於Hajós上述猜想的反例也是Chartrand等人的這個猜想的反例。後來Woodall把這個猜想作了修正重新提出如下:


猜想(Chartrand,Geller和Hedetniemi 1971,Woodall 1990)對所有正整數k,每個滿足
的圖一定含有一個同構於Kk或
的幼圖。


此猜想顯然要弱於哈德威格猜想。
哈德威格猜想的相關證明
1943年,Hadwiger提出了一個關於圖的色數的猜想,除少數幾種情況外,這一猜想至今沒有得到解決。這不足為奇,因為這一猜想的一個實例的真實性等價於平面圖4著色的存在性。這一猜想斷言:色數滿足
的連通圖G能收縮到Kp。等價地,如果G不能收縮到Kp,那么
。該猜想的逆命題為假,即存在可以收縮到Kp且色數小於p的平面圖。例如,把其邊排成一個圈的4階圖有色數2,然而這個圖本身通過收縮一條邊能收縮到K3。


定理1 Hadwiger猜想對於p=5成立若且唯若每個平面圖有4著色。
部分證明 我們只證明,如果Hadwiger猜想對p=5成立,那么每個平面圖G有4著色。設G是平面圖並且假設G能收縮到K5,因為平面圖的收縮還是平面圖,這就推出K5是平面圖,從而得到一條假命題,因此G不能收縮到K5,所以Hadwiger猜想對於p=5為真推出
。

我們已經知道,Hadwiger猜想對於p≤4和p=6為真。下面的定理證明Hadwiger猜想對於p=2,3的情形,至於p=4的情形留作練習。
定理2 設戶p≤3,如果G是色數滿足
的連通圖,那么G能收縮到Kp。

證明 如果p=1,那么通過每條邊的收縮,我們得到K1。如果p=2,那么G至少有一條邊α,除α外收縮所有邊,我們得到K2。現在假設p=3,Χ(G)≥3。因為X(G)≥3,所以G不是二分圖,根據定理可知,G有一條長度為奇數的圈。設γ是G中一條長度最小的奇數圈。則只有連線γ中頂點的邊才是γ的邊,否則我們能找一條長度比γ更短的奇數圈,除γ中的邊外,收縮G中所有的邊而得到γ。我們可以進一步收縮邊,直到獲得K3。