In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies It is known to be true for 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.
In more detail, if all proper colorings of an undirected graph use or more colors, then one can find disjoint connected subgraphs of 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 on vertices as a minor
This conjecture, a far-reaching generalization of the four-color problem, was made by Hugo Hadwiger in 1943 and is still unsolved. call it "one of the deepest unsolved problems in graph theory."
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 a graph to the complete then must have a vertex coloring with colors.
In a minimal of any contracting each color class of the coloring to a single vertex will produce a complete However, this contraction process does not produce a minor 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 in such a way that all the contracted sets are connected.
If denotes the family of graphs having the property that all minors of graphs in can be then it follows from the Robertson–Seymour theorem that can be characterized by a finite set of forbidden minors. Hadwiger's conjecture is that this set consists of a single forbidden
The Hadwiger number of a graph is the size of the largest complete graph that is a minor of (or equivalently can be obtained by contracting edges It is also known as the contraction clique number The Hadwiger conjecture can be stated in the simple algebraic form where denotes the chromatic number
Special cases and partial results
The case is trivial: a graph requires more than one color if and only if it has an edge, and that edge is itself a minor. The case is also easy: the graphs requiring three colors are the non-bipartite graphs, and every non-bipartite graph has an odd cycle, which can be contracted to a 3-cycle, that is, a minor.
In the same paper in which he introduced the conjecture, Hadwiger proved its truth The graphs with no minor are the series–parallel graphs and their subgraphs. Each graph of this type has a vertex with at most two incident edges; one can 3-color any such graph by removing one such vertex, coloring the remaining graph recursively, and then adding back and coloring the removed vertex. Because the removed vertex has at most two edges, one of the three colors will always be available to color it when the vertex is added back.
The truth of the conjecture for implies the four color theorem: for, if the conjecture is true, every graph requiring five or more colors would have a minor and would (by Wagner's theorem) be nonplanar. Klaus Wagner proved in 1937 that the case is actually equivalent to the four color theorem and therefore we now know it to be true. As Wagner showed, every graph that has no minor can be decomposed via clique-sums into pieces that are either planar or an 8-vertex Möbius ladder, and each of these pieces can be 4-colored independently of each other, so the 4-colorability of a -minor-free graph follows from the 4-colorability of each of the planar pieces.
proved the conjecture also using the four color theorem; their paper with this proof won the 1994 Fulkerson Prize. It follows from their proof that linklessly embeddable graphs, a three-dimensional analogue of planar graphs, have chromatic number at most five. Due to this result, the conjecture is known to be true but it remains unsolved for
For , some partial results are known: every 7-chromatic graph must contain either a minor or both a minor and a minor.
Every graph has a vertex with at most incident edges, from which it follows that a greedy coloring algorithm that removes this low-degree vertex, colors the remaining graph, and then adds back the removed vertex and colors it, will color the given graph with colors.