Family 157CombinatoricsLeanNot yet digestedfeatured
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 , where is the largest clique-minor order. Also disproves the fractional Colin de Verdière chromatic bound . In the positive direction, every finite nonempty graph satisfies for a universal constant C.
Manuscripts in this family · 3
A counterexample to Hadwiger's conjecture
Sep 23, 2026·paper.pdfLean
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
Sep 23, 2026·paper.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.
A linear list-coloring bound in terms of the Hadwiger number
Sep 23, 2026·paper.pdf
We prove that every finite nonempty graph G satisfies for an absolute integer C, where is the largest order of a clique minor. This resolves the Linear List Hadwiger conjecture affirmatively.