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

What OpenAI claims

Disproves Hadwiger's conjecture even for fractional coloring: arbitrarily large finite simple graphs with independence number at most two satisfy χ_f(G) > h(G), where h(G) is the largest clique-minor order. Also disproves the fractional Colin de Verdière chromatic bound χ_f(G) ≤ μ(G)+1. In the positive direction, every finite nonempty graph satisfies χ_list(G) ≤ C h(G) for a universal constant C. (Lean)

Papers (3)

1. A counterexample to Hadwiger's conjecture

   23 September 2026 · Preprint, not peer reviewed · PDF

   We disprove Hadwiger's conjecture by constructing arbitrarily large graphs whose chromatic number exceeds their Hadwiger number. The examples have independence number at most two, and even their ordinary fractional chromatic number exceeds their Hadwiger number. Thus they also disprove the fractional-coloring weakening discussed by Reed and Seymour.

2. A counterexample to the Colin de Verdière chromatic conjecture

   23 September 2026 · Preprint, not peer reviewed · PDF

   We disprove the Colin de Verdière chromatic conjecture by constructing graphs whose chromatic number exceeds their Colin de Verdière invariant by more than one. The examples have independence number at most two. In fact, their ordinary fractional chromatic number also exceeds their Colin de Verdière invariant by more than one.

3. A linear list-coloring bound in terms of the Hadwiger number

   23 September 2026 · Preprint, not peer reviewed · PDF

   We prove that every finite nonempty graph G satisfies χ_list(G) ≤ C h(G) for an absolute integer C, where h(G) is the largest order of a clique minor. This resolves the Linear List Hadwiger conjecture affirmatively.

Status

Preprint. The papers have not been independently reviewed. Treat the result as OpenAI's claim until other mathematicians have checked it. If a video exists, it illustrates the statement; it is not the proof.