Hadwiger's conjecture for graphs

About 21 years old · traced to

Let GG be a finite graph and let t∈Nt\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.

References

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.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.