Hadwiger conjecture (graph theory)

Unsolved problem in mathematics:

Does every graph with chromatic number have a -vertex complete graph as a minor?

A graph that requires four colors in any coloring, and four connected subgraphs that, when contracted, form a complete graph, illustrating the case k = 4 of Hadwiger's conjecture

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

This conjecture, a far-reaching generalization of the four-color problem, was made by Hugo Hadwiger in 1943 and is still unsolved.[1] Bollobás, Catlin & Erdős (1980) call it "one of the deepest unsolved problems in graph theory."[2]