Conjecture Fieldbook

GlossaryStudy cards

Hadwiger conjecture

Canonical problem dossier

Every graph with chromatic number t is conjectured to contain the complete graph Kₜ as a minor.

Status
Open
Field
Graph theory
Verification
Reviewed dossier
Source grade
secondary
Reviewed
2026-07-27T18:04:33.834Z
Reviewer
Conjecture Fieldbook maintainers

Formal expression

χ(G)=t⟹?Kt≼G\chi(G)=t\stackrel{?}{\Longrightarrow}K_t\preccurlyeq G

Why it matters

The conjecture would unify graph coloring with structural graph theory and includes the four-color theorem as a special case.

Context and known approaches

The conjecture is known for small t and remains open in general.

Formal boundary

If χ(G)=t, then Kₜ is a minor of G.

Known partial results

Pending review. No structured partial-result note has been added to this dossier.

Equivalent formulations

  • The four-color theorem is the t = 5 case of the graph-theoretic conjecture.

Source trail

  1. Wikipedia — Statement, known cases, and implications.
  2. Wikipedia open-problems list — Composite index by mathematical field.
  3. Wikipedia list subsection — Placement in the accepted revision-pinned living-list snapshot.