Hadwiger conjecture (graph theory)

In graph theory, the Hadwiger conjecture states that if

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

Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph

[1] Bollobás, Catlin & Erdős (1980) call it "one of the deepest unsolved problems in graph theory".

[2] 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

However, this contraction process does not produce a minor of

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

can be characterized by a finite set of forbidden minors.

Hadwiger's conjecture is that this set consists of a single forbidden minor,

[2] The Hadwiger conjecture can be stated in the simple algebraic form

In the same paper in which he introduced the conjecture, Hadwiger proved its truth for

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.

Robertson, Seymour & Thomas (1993) proved the conjecture for

, 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.

In the 1980s, Alexander V. Kostochka[6] and Andrew Thomason[7] both independently proved that every graph with no

A sequence of improvements to this bound have led to a proof of

[8] György Hajós conjectured that Hadwiger's conjecture could be strengthened to subdivisions rather than minors: that is, that every graph with chromatic number

, but Catlin (1979) found counterexamples to this strengthened conjecture for

[9] Erdős & Fajtlowicz (1981) observed that Hajós' conjecture fails badly for random graphs: for any

In this context, it is worth noting that the probability also approaches one that a random

-vertex graph has Hadwiger number greater than or equal to its chromatic number, so the Hadwiger conjecture holds for random graphs with high probability; more precisely, the Hadwiger number is with high probability proportional to

[2] Borowiecki (1993) asked whether Hadwiger's conjecture could be extended to list coloring.

However, the maximum list chromatic number of planar graphs is 5, not 4, so the extension fails already for

, each of which is two-colored, such that each pair of subtrees is connected by a monochromatic edge.

minor are not necessarily sparse, a similar upper bound holds for them as it does for the standard Hadwiger conjecture: a graph with no odd

, it may be possible to prove the existence of larger minors than

One example is the snark theorem, that every cubic graph requiring four colors in any edge coloring has the Petersen graph as a minor, conjectured by W. T. Tutte and announced to be proved in 2001 by Robertson, Sanders, Seymour, and Thomas.