# P23: Hadwiger's conjecture

- ID: `P23`
- Reference: `hadwiger-conjecture`
- Page: https://theoremdb.org/statements/P23
- Record maturity: Reviewed problem with recorded work

## Problem

Every finite graph \(G\) with chromatic number \(\chi(G)=k\) contains the complete graph \(K_k\) as a minor.

### Context

The conjecture connects vertex coloring to graph minors and contains the four-color theorem as a special case.

### Problem setup

- **Definition (The chromatic number).** The chromatic number is the smallest number of colors needed to color vertices so that adjacent vertices receive different colors.
- **Definition (A graph minor).** A graph minor is obtained by deleting vertices or edges and contracting edges.
- **Remark.** The conjecture connects vertex coloring to graph minors and contains the four-color theorem as a special case.

### What 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.

## Status

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](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (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.

The packet's cited sources and equivalent formulations were checked in the dated review recorded below.

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.

### Background and intake notes

- 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-22. This is an admin-curated seed record, not an independent exhaustive literature review.
- The formulation and status were checked against the cited AMS article on 2026-07-22.
- The conjecture is known for chromatic number at most 6. General cases require attention to the distinction between subgraphs, subdivisions, and minors.

- Recorded example: A complete graph K_k has chromatic number k and contains itself as a K_k minor.

### Open directions

- **Route 1** (reported): 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. [1](#reference-1)

### Computational notes

- Exhaustive graph generation can verify bounded orders without settling the universal statement.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `hadwiger-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://www.ams.org/journals/proc/2025-153-08/S0002-9939-2025-16069-5/
   - Also cited at Editorial research route recorded 2026-07-31
   - website; primary source; checked 2026-07-31
   - Source 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.
   - 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.
2. <a id="reference-2"></a>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 https://doi.org/10.1090/proc/16069
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Gives a current neighboring minor theorem and describes the unrestricted Hadwiger conjecture as unresolved.