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

Disproves Hadwiger's conjecture even for fractional coloring: arbitrarily large finite simple graphs with independence number at most two satisfy \chi_f(G)\gt h(G), where h(G) is the largest clique-minor order. Also disproves the fractional Colin de Verdière chromatic bound \chi_f(G)\le\mu(G)+1. In the positive direction, every finite nonempty graph satisfies \chi_{\mathrm{list}}(G)\le C h(G) for a universal constant C. (Lean)

Manuscripts (3)

A counterexample to Hadwiger's conjecture

September 23, 2026 · source · Lean formalization available · cite as \cite{OAI:A-counterexample-to-Hadwigers-conjecture-September-23-2026}

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.

A counterexample to the Colin de Verdière chromatic conjecture

September 23, 2026 · source · cite as \cite{OAI:A-counterexample-to-the-Colin-de-Verdiere-chromatic-conjecture-September-23-2026}

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.

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

September 23, 2026 · source · cite as \cite{OAI:A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number-September-23-2026}

We prove that every finite nonempty graph G satisfies \chi_{\mathrm{list}}(G)\le 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.

Result 157 · Combinatorics. Imported from openai/math, a collection of manuscripts produced by an OpenAI model; results are at different stages of verification. Discussion below is by Lemma members.