TOPICS
Search

Hadwiger Number


The Hadwiger number of a graph G, variously denoted eta(G) (Zelinka 1976, Ivančo 1988) or h(G) (Stiebitz 1990), is the number of vertices in the largest complete minor of G (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 G,

 h(G)>=chi(G),
(1)

where chi(G) the chromatic number of G (Hadwiger 1943).

Forests have h<=2, graphs with treewidth at most 2 have h<=3, planar graphs have h<=4, and apex graphs have h<=5.

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 K_6 among their forbidden minors.

Computing the Hadwiger number of a graph is an NP-hard problem.

For a graph G and its graph complement G^_, the Hadwiger number satisfies

 h(G)+h(G^_)<=6/5n
(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 K_(m,n) is

 h(K_(m,n))=min(m,n)+1
(3)

(Zelinka 1976), of the complete k-partite graph K_(n_1,...,n_k) is

 h(K_(n_1,...,n_k))=min(1+n_1+...+n_(k-1),|_1/2(k+n_1+...+n_k)_|)
(4)

for k>=2 and 1<=n_1<=...<=n_k (Ivančo 1988), and of the wheel complement graph W^__n is

 h(W^__n)=|_(3(n-1))/4_|
(5)

for n>=6, where |_x_| is the floor function (Fowler et al. 2022).


See also

Graph Minor, Hadwiger-Nelson Problem

Explore with Wolfram|Alpha

References

Bollobás, B.; Catlin, P. A.; and Erdős, P. "Hadwiger's Conjecture Is True for Almost Every Graph." European J. Combin. 1, 195-199, 1980.Fowler, L.; and Li, G.; Pavelescu, A. "Complete Minors in Complements of Non-Separating Planar Graphs." 21 Apr 2022. https://arxiv.org/abs/2204.10134v1.Hadwiger, H. "Über eine klassifikation der Streckenkomplexe." Vierteljschr. Naturforsch. Ges. Zürich 88, No. 2, 133-142, 1943.Halin, R. "S-Functions for Graphs." J. Geometry 8, 171-186, 1976.Ivančo, J. "Some Results of the Hadwiger Numbers of Graphs." Math. Slovaca 38, 221-226, 1988.Kostochka, A. V. "On Hadwiger Numbers of a Graph and Its Complement." In Finite and Infinite Sets, Vol. I, II (Eger, 1981) (Ed. A. Hajnal, L. Lovász, and V. T. Sós). Amsterdam: North-Holland, pp. 537-545, 1984.Robertson, N.; Seymour, P. D.; and Thomas, R. "Linkless Embeddings of Graphs in 3-Space." Bull. Amer. Math. Soc. 28, 84-89, 1993.Stiebitz, M. "On Hadwiger Numbers of a Graph and Its Complement." In Contemporary Methods in Graph Theory. Mannheim, Germany: Bibliographisches Inst., pp. 557-568, 1990.Zelinka, B. "Hadwiger Number of Finite Graphs." Math. Slov. 26, 23-30, 1976.

Cite this as:

Weisstein, Eric W. "Hadwiger Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HadwigerNumber.html

Subject classifications