Graph-theory open problems

Hadwiger's conjecture

BM_hadwiger_minor_chromatic

Source: Bondy–Murty, Appendix A, item 41 — Théorie des graphes (French edition, 2025), p. 630; also J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer 2008, Appendix A

Bondy–Murty, Graph Theory, Appendix A, item 41 · Vertex colouring

Bondy–Murty Conjecture — first stated 1943
Attributed to: H. Hadwiger

Status ai-disproved high confidence

OpenAI's manuscript constructs arbitrarily large graphs on $m$ vertices with independence number at most 2 and $h(G) < 26m/75 + 2/3 < m/2 \le \chi_f(G) \le \chi(G)$, where $h(G)$ is the largest order of a clique minor: each is $k$-chromatic for some $k$ (necessarily $k \ge 7$) without a $K_k$ minor.

Cited literature (1)

  • partial Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs (2021)
    Michelle Delcourt, Luke Postle · arXiv preprint · arXiv:2108.01633

    Proves that every K_t-minor-free graph is O(t log log t)-colorable (improving the 1980s bound of O(t√(log t)) by Kostochka and Thomason), making progress toward the weaker Linear Hadwiger’s conjecture but not resolving any new case k ≥ 7 of the original conjecture.

Reviewer notes. Literature status before this model-generated claim: open. Hadwiger's conjecture (every k-chromatic graph has a K_k minor) remains open for k ≥ 7. It is proven for k ≤ 6: the k=5 case is equivalent to the Four Colour Theorem (Wagner 1937) and k=6 was settled by Robertson, Seymour and Thomas (1993). The most significant post-2008 progress is by Delcourt and Postle (arXiv:2108.01633, 2021/2024), who proved that K_t-minor-free graphs are O(t log log t)-colorable, improving the longstanding O(t√(log t)) bound; this advances the weaker ‘Linear Hadwiger’s conjecture’ but does not settle any new case of the original. A 2025 preprint reportedly disproves the Gerards–Seymour odd-minor conjecture (a strengthening of Hadwiger’s conjecture involving odd minors), but that paper could not be URL-verified within the call budget and concerns a distinct statement.

Auto-reviewed 2026-10-07 with claude-opus-5-5 (manual match against the OpenAI catalogue; TeX sources read).

OpenAI manuscript collection ai-disproved

Family 157: Graph coloring, clique minors, and Colin de Verdière invariants

Caveat. This manuscript lies outside the family's Lean formalization, which covers only the companion list-colouring bound.

These manuscripts were produced by an unreleased OpenAI model and released on 2026-10-06 in github.com/openai/math. They have not been peer reviewed. Lean formalizations are OpenAI's own and cover only the scope stated on their scope page; this project has not run or reviewed them. The status above records the claim; before it, the literature review rated this entry open. Its confidence rates whether the manuscript's theorem settles this entry, not whether the manuscript is correct.

Conjecture. Every $k$-chromatic graph has a $K_k$-minor.

Context

Known for $k \le 6$: the case $k = 5$ is equivalent to the Four Colour Theorem (Wagner 1937) and $k = 6$ was settled by Robertson, Seymour and Thomas (1993).

In the book: Conjecture 16.11.

Related records in this index

This conjecture was absent from the Open Problem Garden and arXiv corpora; the records below are the nearest ones.

Editorial notes. Open Problem Garden itself has no page for this conjecture; only the list and fractional variants.

Source

Théorie des graphes (J.A. Bondy, U.S.R. Murty; French edition by Frédéric Havet, 2025), Appendix A « Problèmes ouverts »
Item 41, book p. 630 (PDF p. 646) · https://inria.hal.science/hal-05211979v1 · PDF
English edition: J.A. Bondy, U.S.R. Murty, Graph Theory, GTM 244, Springer 2008, Appendix A.

Related conjectures

  • implies Fractional Hadwiger open Hadwiger's conjecture is equivalent to chi(G) <= had(G) for all G. The standard inequalities are chi_f <= chi and had <= had_f. Hadwiger therefore gives (a) chi_f <= chi <= had, (b) chi <= had <= had_f, and (c) chi_f <= had_f. The target's context says explicitly that these conjectures are weaker than Hadwiger's conjecture.
  • implies Independence number lower bound in K_{t+1}-minor-free graphs ai-disproved Hadwiger's conjecture is equivalent to: every K_{t+1}-minor-free graph has chi <= t (if chi >= t+1, then some (t+1)-chromatic subgraph would have a K_{t+1} minor). A proper t-colouring of an n-vertex graph has a colour class of size >= n/t, so alpha(G) >= n/t. The target node's own context states exactly this implication.
  • implies Seagull problem ai-disproved Take an n-vertex graph with independence number at most 2. Every colour class has at most 2 vertices, so chi >= n/2, and Hadwiger then gives a K_{ceil(n/2)} minor. The target's own context proves this implication and calls the Seagull problem an unproved consequence of Hadwiger's conjecture.
  • related to Coloring and immersion partial The target (Abu-Khzam–Langston) is the immersion analogue of Hadwiger's conjecture, and its context explicitly compares it with Hadwiger's and Hajós' conjectures. Minor containment and immersion containment are incomparable in general: a K_t minor does not yield a K_t immersion, and a K_t immersion does not yield a K_t minor. So neither conjecture implies the other. The connection is documented, but there is no implication.
  • related to Hajós conjecture for $k = 5$ and $k = 6$ open A K_k-subdivision is a K_k-minor, so Hajós for k implies Hadwiger for the same k. The source node covers only k=5,6, and those cases of Hadwiger are already theorems (Wagner + 4CT; Robertson–Seymour–Thomas). So the source does not imply the general Hadwiger node. Hadwiger also does not imply the existence of subdivisions. The relation is related_only: specialization at shared values of k.
  • related to Jorgensen's Conjecture partial The target's context names Hadwiger's conjecture as motivation. The Robertson–Seymour–Thomas proof for K_6-minor-free graphs shows that a minimal counterexample is apex, which comes close to Jørgensen's statement. Still, Jørgensen's conjecture is a structural claim about 6-connected K_6-minor-free graphs. It does not follow from any colouring statement, and it does not imply Hadwiger for general k. So they are related, but neither implies the other.
  • related to List Hadwiger Conjecture ai-proved The target's context presents List Hadwiger as the list-colouring analogue of Hadwiger's conjecture. Hadwiger does not imply it, because list chromatic number can exceed chromatic number; Voigt's example shows that K_5-minor-free graphs need not be 4-list-colourable. List Hadwiger does not imply Hadwiger either, because a ct-list-colouring with c>=1 (and c>=4/3 is necessary by Barát–Joret–Wood) is weaker than a (t-1)-colouring. So the two are related, but neither implies the other.

View in the relation graph — relations are AI-reviewed, not formally verified.