哈德维格数

图 的哈德维格数，有多种表示方法，如 (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)。