The Hadwiger number of a graph , variously denoted (Zelinka 1976, Ivančo 1988) or (Stiebitz 1990), is the number of vertices in the largest complete minor of (Hadwiger 1943, Fowler et al. 2022). The Hadwiger number is also called the contraction clique number (Bollobás et al. 1980) or homomorphism degree (Halin 1976).
The Hadwiger conjecture states that for any loopless graph ,
(1)
|
where the chromatic number of (Hadwiger 1943).
Forests have , graphs with treewidth at most 2 have , planar graphs have , and apex graphs have .
The graphs with Hadwiger number at most five include the apex graphs and the linklessly embeddable graphs (Robertson et al. 1993), both of which have the complete graph among their forbidden minors.
Computing the Hadwiger number of a graph is an NP-hard problem.
For a graph and its graph complement , the Hadwiger number satisfies
(2)
|
(Kostochka 1984, Stiebitz 1990).
The Hadwiger number of a finite simple connected graph with vertex cuts is equal to the maximum of the Hadwiger numbers of its blocks, and the Hadwiger number of a finite simple disconnected graph is equal to the maximum of the Hadwiger numbers of its connected components (Zelinka 1976).
The Hadwiger number of the complete bipartite graph is
(3)
|
(Zelinka 1976), of the complete -partite graph is
(4)
|
for and (Ivančo 1988), and of the wheel complement graph is
(5)
|
for , where is the floor function (Fowler et al. 2022).