Hadwiger number

File:Hadwiger conjecture.svg

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.

In graph theory, the Hadwiger number of an undirected graph Template:Mvar is the size of the largest complete graph that can be obtained by contracting edges of Template:Mvar. Equivalently, the Hadwiger number Template:Math is the largest number Template:Mvar for which the complete graph Template:Mvar is a minor of Template:Mvar, a smaller graph obtained from Template:Mvar by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of Template:MvarTemplate:Sfnp or the homomorphism degree of Template:Mvar.Template:Sfnp It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of Template:Mvar.

The graphs that have Hadwiger number at most four have been characterized by Template:Harvtxt. The graphs with any finite bound on the Hadwiger number are sparse, and have small chromatic number. Determining the Hadwiger number of a graph is NP-hard but fixed-parameter tractable.

Graphs with small Hadwiger number

A graph Template:Mvar has Hadwiger number at most two if and only if it is a forest, for a three-vertex complete minor can only be formed by contracting a cycle in Template:Mvar.

A graph has Hadwiger number at most three if and only if its treewidth is at most two, which is true if and only if each of its biconnected components is a series–parallel graph.

File:Clique-sum.svg

A clique-sum of two planar graphs and the Wagner graph, forming a larger graph with Hadwiger number four.

Wagner's theorem, which characterizes the planar graphs by their forbidden minors, implies that the planar graphs have Hadwiger number at most four. In the same paper that proved this theorem, Template:Harvtxt also characterized the graphs with Hadwiger number at most four more precisely: they are graphs that can be formed by clique-sum operations that combine planar graphs with the eight-vertex Wagner graph.

The graphs with Hadwiger number at most five include the apex graphs and the linklessly embeddable graphs, both of which have the complete graph Template:Math among their forbidden minors.Template:Sfnp

Sparsity

Every graph with Template:Mvar vertices and Hadwiger number Template:Mvar has Template:Tmath edges. This bound is tight: for every Template:Mvar, there exist graphs with Hadwiger number Template:Mvar that have Template:Tmath edges. If a graph Template:Mvar has Hadwiger number Template:Mvar, then all of its subgraphs also have Hadwiger number at most Template:Mvar, and it follows that Template:Mvar must have degeneracy Template:Tmath. Therefore, the graphs with bounded Hadwiger number are sparse graphs.

Coloring

The Hadwiger conjecture states that the Hadwiger number is always at least as large as the chromatic number of Template:Mvar. That is, every graph with Hadwiger number Template:Mvar should have a graph coloring with at most Template:Mvar colors. The case Template:Math is equivalent (by Wagner's characterization of the graphs with this Hadwiger number) to the four color theorem on colorings of planar graphs, and the conjecture has also been proven for Template:Math, but remains unproven for larger values of Template:Mvar.Template:Sfnp

Because of their low degeneracy, the graphs with Hadwiger number at most Template:Mvar can be colored by a greedy coloring algorithm using Template:Tmath colors.

Computational complexity

Testing whether the Hadwiger number of a given graph is at least a given value Template:Mvar is NP-complete,Template:Sfnp from which it follows that determining the Hadwiger number is NP-hard. 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 Template:Math. 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.

Related concepts

The achromatic number of a graph Template:Mvar is the size of the largest clique that can be formed by contracting a family of independent sets in Template:Mvar.

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.Template:Sfnp

Every graph with Hadwiger number Template:Mvar has at most Template:Math cliques (complete subgraphs).Template:Sfnp

Template:Harvtxt defines a class of graph parameters that he calls Template:Mvar-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,Template:Efn 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. The bottom element in this lattice is the Hadwiger number, and the top element is the treewidth.

References

• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .
• .