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.
released 2026-09-23 | 5 theorems · 43 lemmas · 57 proofs · 49,839 words |
PLAY LEVEL 1 »(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.
released 2026-09-23 | 7 theorems · 58 lemmas · 77 proofs · 62,362 words |
PLAY LEVEL 2 »(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.
released 2026-09-23 | 5 theorems · 26 lemmas · 31 proofs · 20,382 words |
PLAY LEVEL 3 »(pdf)
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.