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

1 · The essentials

These manuscripts study how the number of colors a graph needs relates to the tightly connected patterns hidden inside it. A graph is a collection of points joined by edges, and a proper coloring gives different colors to points joined by an edge. The main manuscript constructs arbitrarily large graphs needing more colors than the size of their largest hidden complete pattern, where such a pattern can be obtained by deleting and merging parts of the graph. The mismatch persists even when colors can be shared fractionally rather than assigned one at a time. In these examples, no three points are all unconnected to one another. A companion manuscript reports a similar failure for another numerical measure of a graph, while a third gives a positive bound for coloring when each point has its own list of allowed colors. The main result has a Lean formalization; the supplied source does not report formalizations of the companion results.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, think of assigning time slots to activities, with an edge marking two activities that cannot share a slot. Fractional coloring resembles splitting activities across portions of slots, while list coloring resembles giving each activity its own menu of available slots. This image illustrates the coloring rules, but not the hidden complete patterns used to bound them.

Why it matters

The main result contradicts both Hadwiger's conjecture and the fractional-coloring weakening discussed by Reed and Seymour. The companion results distinguish failure of the proposed exact bounds from the possibility of a bound with a universal multiplier. In particular, the third manuscript shows that the largest clique-minor order still controls list coloring up to such a multiplier.

2 · Going further

For a finite simple graph $G$ , let $χ (G)$ be its chromatic number and let $h (G)$ be the largest order of a clique minor. Hadwiger's conjecture asserts $χ (G) \leq h (G)$ . The main manuscript constructs arbitrarily large graphs with independence number at most two for which even the ordinary fractional chromatic number satisfies $χ_{f} (G) > h (G)$ . Its abstract identifies this as also contradicting the fractional-coloring weakening discussed by Reed and Seymour.

The argument described in the abstract is a construction of counterexamples subject to the strong restriction that no independent set has more than two vertices. It establishes a separation using fractional coloring, not just ordinary coloring. The supplied abstract does not describe the construction or its estimates, so no more detailed mechanism can be extracted from this source. The main result has a Lean formalization.

The second manuscript reports a parallel construction for the Colin de Verdière invariant $μ (G)$ . Its examples again have independence number at most two and satisfy $χ_{f} (G) > μ (G) + 1$ ; the manuscript also reports $χ (G) > μ (G) + 1$ . This addresses a different proposed chromatic bound, rather than merely restating the comparison with $h (G)$ .

In the positive direction, the third manuscript shows that every finite nonempty graph satisfies $χ_{list} (G) \leq C h (G)$ for an absolute integer $C$ . It describes this as an affirmative resolution of the Linear List Hadwiger conjecture. Its abstract states the bound but gives neither the value of $C$ nor the method of argument.

Useful notions

Vertices, edges, and finite simple graphs
Proper graph coloring
Independent sets
Clique minors
Fractional and list coloring

What was known before / what is new

Before

The source presents Hadwiger's conjecture as the proposed comparison between chromatic number and largest clique-minor order. It also identifies a fractional-coloring weakening discussed by Reed and Seymour. The companion manuscripts address the Colin de Verdière chromatic conjecture and the Linear List Hadwiger conjecture; the supplied text gives no further historical account or earlier bounds.

New

The main manuscript supplies arbitrarily large counterexamples to the Hadwiger bound, with independence number at most two, and the failure persists for ordinary fractional coloring. This main result has a Lean formalization. The second manuscript reports the analogous failure of the fractional Colin de Verdière bound, while the third shows a universal linear bound for list coloring in terms of the Hadwiger number.

Limits and assumptions

The main counterexamples are finite simple graphs with independence number at most two; the second manuscript also imposes the independence-number restriction. The positive list-coloring bound applies to every finite nonempty graph and uses an absolute integer C whose value is not supplied. Lean verification is reported for the main result, not for the companion manuscripts, and the source gives no finer account of the formalization's coverage. The abstracts do not supply construction details or argument methods beyond the use of counterexamples, and they identify no further open questions.

Mini glossary

Chromatic number: The chromatic number is the smallest number of colors needed to color vertices so that adjacent vertices have different colors.
Independence number: The independence number is the largest number of vertices that can be chosen with no edges between any two of them.
Clique minor: A clique minor is a complete graph obtainable by deleting vertices or edges and contracting edges.
Hadwiger number: The Hadwiger number is the largest number of vertices in a clique minor of the graph.
Fractional chromatic number: The fractional chromatic number is the minimum total weight of independent sets needed to cover each vertex with weight at least one.
List chromatic number: The list chromatic number is the smallest list size that guarantees a proper coloring from any assignment of allowed-color lists of that size to the vertices.

Keywords : Graph coloring · Clique minors · Colin de Verdière invariant

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

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) \leq μ (G) + 1$ . In the positive direction, every finite nonempty graph satisfies $χ_{list} (G) \leq C h (G)$ for a universal constant C.

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/157.md

Manuscripts in this family

★

A counterexample to Hadwiger's conjecture

23/09/2026

Verified by Lean

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.

PDF GitHub folder Lean formalization

A counterexample to the Colin de Verdière chromatic conjecture

23/09/2026

To be verified

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.

PDF GitHub folder

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

23/09/2026

To be verified

We prove that every finite nonempty graph G satisfies $χ_{list} (G) \leq 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.

PDF GitHub folder