Graph coloring, clique minors, and list bounds

Source and verification

This article explains family 157 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Coloring, minors, and spectral parameters

For a finite nonempty simple graph $G$, the chromatic number $\chi (G)$ is the minimum number of colors in a proper vertex coloring. The independence number $\alpha (G)$ is the largest size of a set containing no edge. If $G$ has $m$ vertices and $\alpha (G)\le 2$, every color class has at most two vertices, so $\chi (G)\ge m/2$.

A $K_t$ minor can be described by $t$ disjoint connected vertex sets, called branch sets, with an edge between every pair of branch sets. The largest possible $t$ is the Hadwiger number $h(G)$. Hadwiger’s conjecture proposes $\chi (G)\le h(G)$.

List coloring permits each vertex $v$ to have its own set $L(v)$ of allowable colors. The list chromatic number ${\chi }_{\mathrm{list}}(G)$ is the least $k$ such that every assignment of lists of size $k$ admits a proper coloring. Ordinary coloring is the special case where every list is the same.

This family contains three manuscripts. Two claim counterexamples to proposed coefficient-one inequalities; the third claims that an absolute constant still controls list coloring by clique-minor size.

🏷️ Connected matchings and a minor obstruction

A connected matching is a set of disjoint edges such that every two of those edges are joined by some further edge of $G$. This is a pairwise condition, stronger than merely requiring their union together with connecting edges to form a connected graph. Write $\mathrm{cm}(G)$ for its maximum size.

First manuscript claim

There are graphs of arbitrarily large order $m$ with $\alpha (G)\le 2$ and $\mathrm{cm}(G)<m/100$. These graphs violate Hadwiger’s conjecture. (OpenAI, 2026)

The passage from a small connected matching to a small minor has an accessible counting proof. In a clique minor, let $a,b,c$ count branch sets of sizes one, two, and at least three. The singleton branch sets form a clique; pairing them produces $\lfloor a/2\rfloor$ disjoint edges. These edges and the $b$ two-vertex branch sets form a connected matching. Hence

$$\begin{array}{c}b+\lfloor a/2\rfloor \le \mathrm{cm}(G),\\ m\ge a+2b+3c.\end{array}$$

The first inequality gives $2a+b\le 4\mathrm{cm}(G)+2$. Since $3(a+b+c)\le m+2a+b$, we obtain

$$h(G)\le \frac{m+4\mathrm{cm}(G)+2}{3}.$$

For the proposed examples, this is less than $26m/75+2/3$, and hence less than $m/2$ for $m\ge 5$. The elementary color-class bound then gives $h(G)<\chi (G)$.

The difficult construction keeps the complement triangle-free, which ensures $\alpha (G)\le 2$, while introducing enough missing cross-edges to spoil every large connected matching. Two disjoint edges fail to be joined precisely when all four cross-pairs are missing. The paper builds these four-edge conflict patterns using dependent random data, entropy estimates, and controlled sampling.

The dependence matters: an adversarial matching can choose correlated endpoints. Estimates for independently sampled endpoint pairs would not cover all matchings. The source also retains rare compatibility events during limiting arguments; throwing them away merely because their probability tends to zero would remove constraints needed by the construction.

🏷️ A stronger spectral counterexample

The Colin de Verdière invariant $\mu (G)$ is defined through real symmetric matrices $M$ indexed by vertices. Off-diagonal entries are negative on edges and zero on nonedges; diagonal entries are unrestricted. The matrix must have exactly one negative eigenvalue and satisfy the strong Arnold property: the only symmetric $X$ with $MX=0$, zero diagonal, and $X_{uv}=0$ on every edge is $X=0$. The invariant is the largest possible nullity of such a matrix.

Second manuscript claim

There are arbitrarily large graphs with $\alpha (G)\le 2$ and $\mu (G)+1<m/2\le \chi (G)$. (OpenAI, 2026b)

Because $h(G)\le \mu (G)+1$, a counterexample to the Hadwiger inequality alone would not imply this stronger conclusion. The second paper instead proves a rank bound for every matrix with the specified off-diagonal signs and exactly one negative eigenvalue, even without the strong Arnold property. A rank greater than $m/2+1$ forces nullity plus one below $m/2$.

The construction starts from a finite graph with several robust conflict properties, then replaces each vertex by a clique. The base graph is fixed before the clique size tends to infinity. The matrix proof organizes possible low-rank representations through a finite tree of limiting configurations. One stage extracts rank from matching coordinates; another obtains additional independent positive directions. Both stages are needed to cross the required rank threshold.

🏷️ A universal linear list-coloring bound

Third manuscript claim

There is an absolute constant $C$ such that every finite nonempty simple graph satisfies ${\chi }_{\mathrm{list}}(G)\le Ch(G)$. (OpenAI, 2026c)

The constant is not asserted to be one, and the paper does not optimize it. The bound concerns arbitrary lists, whose union can be much larger than the list size.

The proof first establishes a linear list bound for relatively small graphs excluding a fixed clique minor. It then divides the global color palette into bins. A stable set of vertices can use different allowable colors from the same bin; different bins have disjoint palettes and therefore cannot create cross-bin color conflicts. A fractional halving argument controls the number of bins needed.

For larger graphs, a recursive decomposition either finds useful separation or constructs a rooted clique minor. The central bookkeeping issue is list loss. Deleting a long path one vertex at a time could consume too many colors; the source charges losses to the path’s structural role and its recorded history instead of its length. Small connected districts support the minor construction, and a three-district recursion preserves the pairwise connections required at later stages.

The three papers therefore address different levels of a comparison: the proposed equality-scale control fails, while control up to a universal factor is claimed to survive even for lists.

🏷️ Key steps and proof outlines

Global palette reservation controls deletion loss

In this additive deletion lemma, $d\ge 0$ is a fixed integer and $t$ is a sufficiently large integer depending on $d$. This range ensures that the palette-reservation union bound is strictly below one.

The list-coloring companion needs to remove structured vertex sets while losing only $O(t)$ colors, independently of graph order and total palette size. One key lemma assumes $h(P)<t$, a small set $X$ with $|X|\le t^{11/10}$, and a disjoint set $Y$ whose induced graph is $dt$-degenerate and gives every remaining vertex at most $dt$ neighbors in $Y$. If $s={\chi }_{\mathrm{list}}(P-X-Y)$, the target list size is $u=s+(4L+d+5)t$, where $L$ is the small-graph list-bound constant.

Reserve each color in the entire finite palette independently with probability $2Lt/u$, making the reservation global across all occurrences of that color. Every vertex then has a binomial number of reserved entries of mean $2Lt$, regardless of overlaps between lists. The proof needs a lower bound $Lt$ only on vertices in $X$ and an upper bound $4Lt$ only on vertices with at least $t$ neighbors in $X$.

The source’s minor lemma bounds the latter exceptional set by $\left(\genfrac{}{}{0ex}{}{|X|}{2}\right)$. Thus only polynomially many vertices are tested, even if $P$ is enormous. Chernoff estimates give exponentially small failure probability in $t$, and a union bound fixes a successful reservation. Independence between different vertices’ bad events is unnecessary. (OpenAI, 2026c)

Three successive colorings use only actual neighbor losses

Color $P[X]$ using its reserved entries and the small-graph theorem. At a vertex with many neighbors in $X$, all colors actually lost are reserved, so at most $4Lt$ disappear. At any other vertex, fewer than $t$ disappear because there are fewer than $t$ such neighbors. It is not necessary to delete every globally reserved color from all remaining lists.

At least $s+(d+4)t$ entries remain under the source’s uniform slack bound. Greedy degeneracy coloring now colors $P[Y]$. Deleting its colors from the final remainder loses at most $dt$ entries per vertex, leaving at least $s$. The definition of $s$ colors that remainder. Both pruning steps remove colors actually used on adjacent earlier vertices, so the three colorings combine properly. This proves the additive deletion inequality, which supports the later separator and district recursion without charging colors one vertex at a time along a long path.

The two counterexamples need different graph-to-matrix interfaces

For the Hadwiger construction, the required graph property is a small maximum connected matching together with $\alpha \le 2$. The branch-set count then gives $h(G)\le (m+4\mathrm{cm}(G)+2)/3$, while every coloring needs at least $m/2$ colors. The hard source construction must therefore spoil every large matching by a pair of edges with all four cross-pairs missing, while keeping the complement triangle-free. Its dependent sampling estimates handle endpoints selected adversarially by the matching; an estimate for independently selected pairs would not prove this universal property. (OpenAI, 2026a)

The spectral companion requires more robust base-graph properties: conflicting pairs across matching classes, conflicting edge-point pairs, and cross holes between large vertex sets. It fixes that base graph before taking a large clique blow-up. A well-signed symmetric matrix with one negative eigenvalue admits a Gram representation for the form $-x_0{y}_0+{\sum }_{i\ge 1}{x}_i{y}_i$. Restrictions and coefficient pullbacks retain at most one negative direction, permitting its two-stage normalization.

A positive definite block $D$ with nonpositive off-diagonal entries has an entrywise nonnegative inverse square root. To see this, choose $c>{\lambda }_{\max }(D)$ and put $A=I-D/c$. Then $A$ is entrywise nonnegative with spectrum in $[0,1)$, and

$$D^{-1/2}=c^{-1/2}\sum _{k\ge 0}\frac{\left(\genfrac{}{}{0ex}{}{2k}{k}\right)}{4^k}{A}^k.$$

Every coefficient is positive, and the constant term gives a positive diagonal. Such normalization preserves the relevant sign constraints while producing bounded Gram configurations. The matrix-tree lemmas organize their limits; one stage supplies almost disjoint matching coordinates and the next additional positive directions. Together they force rank greater than $ms/2+1$ in a blow-up with $ms$ vertices. This is stronger than a clique-minor exclusion and holds without assuming the strong Arnold property, hence bounds every matrix allowed in the definition of $\mu$. (OpenAI, 2026b)

The linear list theorem and the two counterexamples are consequently compatible statements with separate proof obligations: a universal constant-factor upper bound can survive even though coefficient-one comparisons fail.

See Also

• Complete-graph crossing numbers also uses rank and dimension inequalities to turn geometric data into graph bounds.
• Strong thin trees introduces a different graph parameter controlled by simultaneous constraints on all cuts.

🏷️ Manuscripts and verification scope

• A counterexample to Hadwiger’s conjecture — pinned manuscript and companion source.
• A counterexample to the Colin de Verdière chromatic conjecture — pinned manuscript and companion source.
• A linear list-coloring bound in terms of the Hadwiger number — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The page documents only the universal linear list-coloring bound. It does not document either counterexample manuscript in this family. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. A counterexample to Hadwiger’s conjecture.

🐻  OpenAI 2026b. A counterexample to the Colin de Verdière chromatic conjecture.

🐻  OpenAI 2026c. A linear list-coloring bound in terms of the Hadwiger number.