[#P23] Hadwiger's conjecture
Problem. Every finite graph \(G\) with chromatic number \(\chi(G)=k\) contains the complete graph \(K_k\) as a minor.
1Context
The conjecture connects vertex coloring to graph minors and contains the four-color theorem as a special case.
2Problem setup
Definition 1 (The chromatic number). The chromatic number is the smallest number of colors needed to color vertices so that adjacent vertices receive different colors.
Definition 2 (A graph minor). A graph minor is obtained by deleting vertices or edges and contracting edges.
Remark 1. The conjecture connects vertex coloring to graph minors and contains the four-color theorem as a special case.
3What counts as a solution
- Prove the clique-minor conclusion for every finite graph, or give a finite graph whose chromatic number exceeds the order of its largest complete minor.
1Status
Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: The conjecture is proved through the cases equivalent to at most six colors. The linked 2025 article proves a triangle-free minor-avoiding independence result and still treats the general finite-graph statement as open. Exact unresolved remainder: Prove that every finite graph has a complete minor of order at least its chromatic number, or give a finite graph whose chromatic number exceeds its largest complete minor.[1][2]
1Packet records
Recent contributions
These records are attached to this problem after the current published packet. Each badge shows its current verification or packet-review step.
Notes and companion material
Original intake status. The cited 2025 AMS article calls Hadwiger's conjecture celebrated and treats it as unresolved. The source and public status were checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.
- The conjecture is known for chromatic number at most 6. General cases require attention to the distinction between subgraphs, subdivisions, and minors.
Recorded example 1. A complete graph K_k has chromatic number k and contains itself as a K_k minor.
Computational notes
- Exhaustive graph generation can verify bounded orders without settling the universal statement.
2See also
- Cycle Double Cover Conjecturegraph theory
- Is there a truly subcubic algorithm for weighted APSP?graph theory
- The Total Coloring Conjecturegraph theory
How to cite
TheoremDB contributors, “Hadwiger's conjecture,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/hadwiger-conjectureThis page as plain text: hadwiger-conjecture.md
This problem includes 2 records joined by 2 typed links, sourced from ams.org[1], current as of July 31, 2026.
1References
- Packet source. Independence number in triangle-free graphs avoiding a clique minor. Zdenek Dvorak and Liana Yepremyan, Proceedings of the American Mathematical Society 153 (2025), abstract and introduction. Zdenek Dvorak and Liana Yepremyan, Proceedings of the American Mathematical Society 153 (2025), abstract and introduction. ↗website · primary source · checked 2026-07-31Source use: original summary.The cited 2025 AMS article calls Hadwiger's conjecture celebrated and treats it as unresolved. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.For Hadwiger's conjecture, the reviewed source scope is Zdenek Dvorak and Liana Yepremyan, Proceedings of the American Mathematical Society 153 (2025), abstract and introduction. The packet makes no inference beyond that cited scope.Source named by the research packet.
- Zdeněk Dvořák and Liana Yepremyan, “Independence number in triangle-free graphs avoiding a clique minor”. Proceedings of the American Mathematical Society 153(8) (2025), 3185-3195. DOI 10.1090/proc/16069. abstract and introduction. ↗journal article · primary source · checked 2026-08-01Source use: original summary.Gives a current neighboring minor theorem and describes the unrestricted Hadwiger conjecture as unresolved.
An original CC0 restatement prepared by TheoremDB maintainers.