Hadwiger Conjecture (graph Theory) - Equivalent Forms

Equivalent Forms

An equivalent form of the Hadwiger conjecture (the contrapositive of the form stated above) is that, if there is no sequence of edge contractions (each merging the two endpoints of some edge into a single supervertex) that brings graph G to the complete graph K_k, then G must have a vertex coloring with k − 1 colors.

Note that, in a minimal k-coloring of any graph G, contracting each color class of the coloring to a single vertex will produce a complete graph K_k. However, this contraction process does not produce a minor of G because there is (by definition) no edge between any two vertices in the same color class, thus the contraction is not an edge contraction (which is required for minors). Hadwiger's conjecture states that there exists a different way of properly edge contracting sets of vertices to single vertices, producing a complete graph K_k, in such a way that all the contracted sets are connected.

If F_k denotes the family of graphs having the property that all minors of graphs in F_k can be (k − 1)-colored, then it follows from the Robertson–Seymour theorem that F_k can be characterized by a finite set of forbidden minors. Hadwiger's conjecture is that this set consists of a single forbidden minor, K_k.