In graph theory, the Hadwiger conjecture states that if G {\displaystyle G} is loopless and has no K t {\displaystyle K_{t}} minor then its chromatic number satisfies χ ( G ) < t {\displaystyle \chi (G)<t} . It is known to be true for 1 ≤ t ≤ 6 {\displaystyle 1\leq t\leq 6} . The conjecture is a generalization of the four color theorem and is considered to be one of the most important and challenging open problems in the field. Reversing the implication, the conjecture can equivalently be stated in the following form. According to it, if all proper colorings of an undirected graph G {\displaystyle G} use k {\displaystyle k} or more colors, then one can find k {\displaystyle k} disjoint connected subgraphs of G {\displaystyle G} such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph K k {\displaystyle K_{k}} on k {\displaystyle k} vertices as a minor of G {\displaystyle G} . The conjecture was made by Hugo Hadwiger in 1943. Bollobás, Catlin & Erdős (1980) call it "one of the deepest unsolved problems in graph theory".
Equivalent forms One form of the Hadwiger conjecture is that, if there is no sequence of edge contractions (each merging the two endpoints of some edge into a single supervertex) that brings a graph G {\displaystyle G} to the complete graph K k {\displaystyle K_{k}} , then G {\displaystyle G} must have a vertex coloring with k − 1 {\displaystyle k-1} colors. Equivalently (the contrapositive of the same statement), if a given graph has no such coloring, then there is a way of contracting edges to produce K k {\displaystyle K_{k}} as a graph minor. In a minimal k {\displaystyle k} -coloring of any graph G {\displaystyle G} , contracting each color class of the coloring to a single vertex will produce a complete graph K k {\displaystyle K_{k}} . However, this contraction process does not produce a minor of G {\displaystyle 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 {\displaystyle K_{k}} , in such a way that all the contracted sets are connected. If F k {\displaystyle {\mathcal {F}}_{k}} denotes the family of graphs having the property that all minors of graphs in F k {\displaystyle {\mathcal {F}}_{k}} can be ( k − 1 ) {\displaystyle (k-1)} -colored, then it follows from the Robertson–Seymour theorem that F k {\displaystyle {\mathcal {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 {\displaystyle K_{k}} . The Hadwiger number h ( G ) {\displaystyle h(G)} of a graph G {\displaystyle G} is the size k {\displaystyle k} of the largest complete graph K k {\displaystyle K_{k}} that is a minor of G {\displaystyle G} (or equivalently can be obtained by contracting edges of G {\displaystyle G} ). It is also known as the contraction clique number of G {\displaystyle G} . The Hadwiger conjecture can be stated in the simple algebraic form χ ( G ) ≤ h ( G ) {\displaystyle \chi (G)\leq h(G)} where χ ( G ) {\displaystyle \chi (G)} denotes the chromatic number of G {\displaystyle G} .
… excerpt ends here. Continue reading the full article.
