Hadwiger number

Determining the Hadwiger number of a graph is NP-hard but fixed-parameter tractable.

This bound is tight: for every k, there exist graphs with Hadwiger number k that have ⁠

However, the problem is fixed-parameter tractable: there is an algorithm for finding the largest clique minor in an amount of time that depends only polynomially on the size of the graph, but exponentially in h(G).

[7] Additionally, polynomial time algorithms can approximate the Hadwiger number significantly more accurately than the best polynomial-time approximation (assuming P ≠ NP) to the size of the largest complete subgraph.

[7] The achromatic number of a graph G is the size of the largest clique that can be formed by contracting a family of independent sets in G. Uncountable clique minors in infinite graphs may be characterized in terms of havens, which formalize the evasion strategies for certain pursuit–evasion games: if the Hadwiger number is uncountable, then it equals the largest order of a haven in the graph.

[9] Halin (1976) defines a class of graph parameters that he calls S-functions, which include the Hadwiger number.

These functions from graphs to integers are required to be zero on graphs with no edges, to be minor-monotone,[a] to increase by one when a new vertex is added that is adjacent to all previous vertices, and to take the larger value from the two subgraphs on either side of a clique separator.

The set of all such functions forms a complete lattice under the operations of elementwise minimization and maximization.

A graph with four connected subgraphs that, when contracted, form a complete graph. It has no five-vertex complete minor by Wagner's theorem , so its Hadwiger number is exactly four.
A clique-sum of two planar graphs and the Wagner graph, forming a larger graph with Hadwiger number four.