Hadwiger's conjecture for graphs

From papers

Let GG be a finite graph and let tNt\in\mathbb{N}. A minor of GG is a graph obtainable from GG by a sequence of vertex deletions, edge deletions, and edge contractions; write χ(G)\chi(G) for the chromatic number and KtK_t for the complete graph on tt vertices. Hadwiger's conjecture. If χ(G)>t\chi(G)>t, then GG has KtK_t as a minor. Equivalently, if GG does not have KtK_t as a minor, then χ(G)<t\chi(G)<t. This is a central open problem in graph theory, formulated by Hadwiger in 1943; the source presents it as an open conjecture, while the paper studies its analogue for hypergraphs.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dominic van der Zypen, “Hadwiger's conjecture for hypergraphs”, arXiv:2607.27243 (2026).

Additional references

60 papers in this index state this conjecture (2005–2026). The statement above is taken from the most recent of them; the others are arXiv:2605.28159, arXiv:2512.20392, arXiv:2512.17114, arXiv:2512.01401, arXiv:2511.09673, arXiv:2510.12567, arXiv:2510.12564, arXiv:2508.08119, arXiv:2507.03244, arXiv:2505.10097, arXiv:2505.03851, arXiv:2502.10227, and 47 more.

Solutions 0

No solutions have been posted yet.