Hadwiger Conjecture (graph Theory) - Hadwiger Number

The Hadwiger number h(G) of a graph G is the size k of the largest complete graph K_k that is a minor of G (or equivalently can be obtained by contracting edges of G). It is also known as the contraction clique number of G. The Hadwiger conjecture can be stated in the simple algebraic form χ(G) ≤ h(G) where χ(G) denotes the chromatic number of G. A related concept, the achromatic number of G, is the size of the largest clique that can be formed by contracting a family of independent sets in G).

Determining the Hadwiger number of a given graph is NP-complete but 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). 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 clique in a graph.

It is known that every graph G with h(G) = k has a vertex with at most O(k √log k) incident edges. By applying a greedy coloring algorithm that removes this low-degree vertex, colors the remaining graph, and then adds back the removed vertex and colors it, one can show that χ(G) = O(k √log k).