哈德維格數

圖 的哈德維格數，有多種表示方法，如 (Zelinka 1976, Ivančo 1988) 或 (Stiebitz 1990)，是指圖 的最大完全次圖中的頂點數 (Hadwiger 1943, Fowler et al. 2022)。哈德維格數也稱為收縮團數 (Bollobás et al. 1980) 或同態度 (Halin 1976)。

哈德維格猜想指出，對於任何無環圖 ,

(1)

其中 是圖 的著色數 (Hadwiger 1943)。

森林的哈德維格數 ，樹寬至多為 2 的圖的哈德維格數 ，平面圖的哈德維格數 ，頂點圖的哈德維格數 。

哈德維格數至多為 5 的圖包括頂點圖和無連線可嵌入圖 (Robertson et al. 1993)，這兩者都以完全圖 作為其禁止次圖。

計算圖的哈德維格數是一個 NP 難問題。

對於圖 及其補圖 ，哈德維格數滿足

(2)

(Kostochka 1984, Stiebitz 1990)。

具有頂點割的有限簡單連通圖的哈德維格數等於其塊的哈德維格數的最大值，有限簡單非連通圖的哈德維格數等於其連通分量的哈德維格數的最大值 (Zelinka 1976)。

完全二部圖 的哈德維格數是

(3)

(Zelinka 1976)，完全 -部圖 的哈德維格數是

(4)

對於 和 (Ivančo 1988)，輪補圖 的哈德維格數是

(5)

對於 ，其中 是向下取整函式 (Fowler et al. 2022)。