Hadwiger conjecture (graph theory)

Unsolved problem in mathematics
Does every graph with <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a> 
 
 
 
 k
 
 
 {\displaystyle k}
 
 have a 
 
 
 
 k
 
 
 {\displaystyle k}
 
-vertex <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> as a <a href="/facts/Minor_(graph_theory)/qn5eI22T">minor</a>?
<a href="/facts/List_of_unsolved_problems_in_mathematics/RroxGPpP">More unsolved problems in mathematics</a>

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, the Hadwiger conjecture states that if 
 
 
 
 G
 
 
 {\displaystyle G}
 
 is <a href="/facts/Loop_(graph_theory)/jCuevIad">loopless</a> and has no 
 
 
 
 
 K
 
 t
 
 
 
 
 {\displaystyle K_{t}}
 
 <a href="/facts/Graph_minor/qn5eI22T">minor</a> then its <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a> 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 <a href="/facts/Four_color_theorem/HTS4Nway">four color theorem</a> and is considered to be one of the most important and challenging open problems in the field.
In more detail, if all <a href="/facts/Graph_coloring/J6HoBfP0">proper colorings</a> of an <a href="/facts/Undirected_graph/kw3eIBUe">undirected graph</a> 
 
 
 
 G
 
 
 {\displaystyle G}
 
 use 
 
 
 
 k
 
 
 {\displaystyle k}
 
 or more colors, then one can find 
 
 
 
 k
 
 
 {\displaystyle k}
 
 <a href="/facts/Disjoint_set/nLr8XRVd">disjoint</a> <a href="/facts/Connected_graph/FSNjsYhz">connected</a> <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">subgraphs</a> of 
 
 
 
 G
 
 
 {\displaystyle G}
 
 such that each subgraph is connected by an <a href="/facts/Edge_(graph_theory)/W0MqKkyE">edge</a> to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> 
 
 
 
 
 K
 
 k
 
 
 
 
 {\displaystyle K_{k}}
 
 on 
 
 
 
 k
 
 
 {\displaystyle k}
 
 vertices as a <a href="/facts/Minor_(graph_theory)/qn5eI22T">minor</a> of 
 
 
 
 G
 
 
 {\displaystyle G}
 
.
The conjecture was made by <a href="/facts/Hugo_Hadwiger/7Bsejnf4">Hugo Hadwiger</a> in 1943. Bollobás, Catlin & Erdős (1980) call it "one of the deepest unsolved problems in graph theory".

Hadwiger conjecture (graph theory) open-in-new

Hadwiger conjecture (graph theory)