OpenAI research collection · 3 manuscripts · Source checked 2026-10-19
The idea in plain language
How many colours does a network need if connected points must differ? This family claims counterexamples to an expected relationship between colouring and complete networks obtained by contracting edges, alongside a separate positive bound for list colouring.
Why it matters
A counterexample can be as important as a proof of a conjecture: it identifies where a plausible general rule fails.
Read the technical source claim
Disproves Hadwiger's conjecture even for fractional coloring: arbitrarily large finite simple graphs with independence number at most two satisfy \chi_f(G)> h(G), where h(G) is the largest clique-minor order. Also disproves the fractional Colin de Verdière chromatic bound \chi_f(G)≤\mu(G)+1. In the positive direction, every finite nonempty graph satisfies \chi_{list}(G)≤ C h(G) for a universal constant C.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
A counterexample to Hadwiger's conjecture
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…
Full source abstract
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.
This PDF is listed in OpenAI's formalization catalogue. See the scope and dependencies before interpreting coverage.
A counterexample to the Colin de Verdière chromatic conjecture
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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
A linear list-coloring bound in terms of the Hadwiger number
We prove that every finite nonempty graph G satisfies \chi_{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.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.