Graph coloring and clique minors after the coefficient-one conjectures

← All digests

Family 157 · Combinatorics
Importance 5/5 · Provisional editorial rating
Sources consulted 2026-10-11

1. The question

If a graph needs many colors, must it contain a comparably complicated complete graph after suitable contractions? Hadwiger’s conjecture predicts an exact answer: the number of colors never exceeds the largest complete minor. It connects the everyday rule that adjacent vertices receive different colors to the global structure created by contracting connected regions.

Family 157 contains three manuscripts with complementary conclusions. M1 claims counterexamples to Hadwiger’s exact inequality. M2 claims counterexamples to a related bound using the Colin de Verdière matrix invariant. Both failures persist when coloring is relaxed to fractional coloring. M3 supplies a positive replacement: the list chromatic number is at most a universal constant times the complete-minor number.

The resulting picture has an important distinction. The proposed coefficient one fails, according to the sources, while a constant independent of the graph still suffices, even for a more demanding coloring problem.

2. Background and essential definitions

A graph here is finite, simple and nonempty. “Simple” excludes loops and repeated edges. A proper coloring assigns different colors to adjacent vertices, and $\chi(G)$ is the minimum number needed. An independent set contains no adjacent pair; $\alpha(G)$ is its maximum size.

A complete graph $K_t$ has all possible edges between its $t$ vertices. A $K_t$ minor in $G$ can be represented by $t$ disjoint connected vertex sets, called branch sets, such that every two branch sets have at least one joining edge. Contracting each branch set gives the complete graph. The largest possible $t$ is the Hadwiger number $h(G)$.

Three notions of coloring

Fractional coloring gives nonnegative weights $w_I$ to independent sets, requiring each vertex to receive total weight at least one. Its optimum is

$$\chi_f(G)=\min\left\{\sum_Iw_I: \sum_{I\ni v}w_I\ge1\text{ for every }v\right\}.$$

An ordinary coloring assigns weight one to each color class, so $\chi_f(G)\le\chi(G)$. Summing the coverage conditions also gives

$$\chi_f(G)\ge\frac{|V(G)|}{\alpha(G)}.$$

Thus if no independent set has more than two vertices, even fractional coloring costs at least half the graph’s order.

List coloring goes in the other direction. Each vertex receives its own set of allowable colors. The list chromatic number $\chi_{\mathrm{list}}(G)$ is the least $k$ that guarantees a proper coloring for every assignment of lists of size at least $k$. Consequently,

$$\chi_f(G)\le\chi(G)\le\chi_{\mathrm{list}}(G).$$

A matrix measure of graph complexity

The Colin de Verdière invariant $\mu(G)$ maximizes the nullity, or kernel dimension, of certain real symmetric matrices indexed by the vertices. Off-diagonal entries must be negative on edges and zero on nonedges. The matrix must have exactly one negative eigenvalue, counted with multiplicity.

It must also satisfy the Strong Arnold Property: the only symmetric matrix $X$ with $MX=0$, zero diagonal, and zero entries at edges is $X=0$. This is a nondegeneracy requirement, not an extra restriction on the graph. A fundamental comparison is $h(G)\le\mu(G)+1$.

3. Development history and previous partial results

Hadwiger’s 1943 conjecture asserts $\chi(G)\le h(G)$. Its small-minor cases connect closely to the Four-Color Theorem. The case excluding a $K_6$ minor was established by Robertson, Seymour and Thomas through structural graph theory. These successes encouraged the possibility of one universal exact inequality.

For large excluded minors, density methods of Kostochka and Thomason gave coloring bounds of order $t\sqrt{\log t}$ for graphs with no $K_t$ minor. Such a bound follows by repeatedly removing a low-degree vertex and coloring in reverse order. Norin, Postle and Song improved on this route’s limit. Later work by Delcourt and Postle, and then Liu and Luo, reduced the extra logarithmic factors further, as described in the sources.

Fractional coloring had an earlier linear result. Reed and Seymour’s 1998 theorem gives $\chi_f(G)\le2h(G)$. They also discussed the coefficient-one fractional version. Their theorem did not automatically yield a linear ordinary coloring, since selecting independent sets repeatedly can accumulate an unwanted factor depending on the number of vertices.

List coloring introduces additional obstacles because available palettes differ across vertices. Postle’s work on the list version approached a linear bound through connectivity and minor constructions. Known examples already require a universal list-coloring coefficient of at least two, so coefficient one was not the appropriate target for that variant.

The Colin de Verdière conjecture grew from spectral graph theory. Small values of $\mu$ characterize familiar embedding classes, including planar graphs at $\mu\le3$. The inequality $\chi(G)\le\mu(G)+1$ was a natural attempt to extend these connections. Since $h(G)\le\mu(G)+1$, it is weaker than Hadwiger’s ordinary inequality, and its failure requires more than just any Hadwiger counterexample.

4. What the new manuscripts claim

M1: too few complete minors for the coloring cost

M1 constructs arbitrarily large graphs of order $m$ with $\alpha(G)\le2$ and a small connected matching. A matching consists of disjoint edges; here it is called connected when every two matching edges have an edge joining their endpoint sets. This is stronger than their union merely belonging to a connected graph.

Writing $\operatorname{cm}(G)$ for its maximum size, the construction has $\operatorname{cm}(G)<m/100$. The source’s counting bound then yields, for its sufficiently large examples,

$$h(G)<\frac{26m}{75}+\frac23 <\frac m2\le\chi_f(G)\le\chi(G).$$

Thus the same family violates both ordinary Hadwiger and its fractional-coloring weakening. The minor parameter remains the ordinary one; it has not been replaced by a fractional minor notion.

M2: failure of the spectral coloring bound

M2 constructs arbitrarily large graphs with

$$\alpha(G)\le2, \qquad \mu(G)+1<\frac{|V(G)|}{2}\le\chi_f(G).$$

It proves a stronger matrix obstruction than the definition of $\mu$ requires: every well-signed matrix with one negative eigenvalue has rank exceeding half the graph’s order plus one, even without imposing the Strong Arnold Property. Rank–nullity turns this into the required upper bound on $\mu$.

M3: a linear bound survives

For every finite nonempty simple graph, M3 asserts

$$\chi_{\mathrm{list}}(G)\le C h(G)$$

for one absolute integer $C$. The constant does not depend on graph order, list assignment or total palette size. It is not optimized. This also gives $\chi(G)\le Ch(G)$, and the comparison with $\mu$ gives a linear list bound in $\mu(G)+1$.

5. Why the advance matters

Importance: 5/5. Hadwiger’s conjecture is a central proposed bridge between coloring and graph minors. Refuting its ordinary and fractional forms, refuting the related spectral inequality, and establishing a universal linear replacement would substantially reshape that bridge.

The positive result matters as much as the counterexamples. It says the parameters still control one another at the scale of a constant factor. The obstruction is to an exact numerical prediction, while the larger structural relationship survives.

The examples with independence number at most two are especially informative. Their coloring lower bound is transparent: every color class is tiny. The difficult work lies in keeping complete minors or admissible matrix kernels below the level suggested by that coloring cost. This identifies a concrete way the conjectured relationship can fail.

6. The main idea

Force missing connections without allowing large independent sets

The counterexample constructions begin with a carefully designed relation of “holes,” meaning missing edges. That relation is triangle-free. Its complement therefore has no independent triple and automatically requires at least half as many fractional colors as vertices.

The harder condition concerns pairs of graph edges. If all four cross-pairs between two disjoint edges are holes, the edges cannot occur together in a connected matching. Algebraic data over a finite field create many such conflicts while keeping the hole relation triangle-free. The triangle exclusion comes from a parity contradiction; forcing enough four-hole configurations requires more elaborate distribution estimates.

Probabilistic sampling produces a finite graph. A container argument organizes large candidate edge families by a controlled collection of descriptions, allowing the conflict estimates to hold across all relevant candidates. A container here is a larger structured family used to cover possible configurations, not a graph vertex.

M2 strengthens these conflict properties to distinguish classes of matching edges and to compare edges against separate vertex sets. It then replaces each base vertex by a clique. For these enlarged graphs, the source’s matrix argument forces additional independent directions in any admissible matrix, raising rank and lowering nullity. This is a separate route from merely bounding connected matchings.

Make fractional structure respect actual color lists

M3 starts with small minor-free graphs. It partitions the union of all available colors into bins, using the same bin assignment for a color wherever it occurs. A vertex can use only bins containing one of its own colors.

The method selects independent sets among vertices eligible for a bin. Vertices in one selected set may choose different colors from that bin, since they are nonadjacent. Different bins cannot introduce a shared-color conflict. Repeated stages reduce the remaining fractional-coloring demand while using only a linear total number of bins.

The passage to arbitrarily large graphs uses connectivity, controlled deletion and recursive minor constructions. Long connecting paths cannot simply be charged by their numbers of vertices, which may be enormous. The source instead controls their interaction with the remaining lists through their structural properties. A graph that continues to resist the desired coloring must then supply the forbidden clique minor.

7. Scope, limitations, and open questions

The counterexamples exist at arbitrarily large orders; the statements do not identify a smallest counterexample or provide a small numerical graph to inspect. M1’s fixed bound $\operatorname{cm}(G)<m/100$ does not say $\operatorname{cm}(G)=o(m)$, so it leaves open weaker universal lower bounds with sufficiently small positive coefficients.

M3 does not determine the best constant $C$. Known list-coloring lower bounds and the new ordinary counterexamples constrain possible constants differently. Neither the fractional theorem with factor two nor these constructions alone identifies the optimal ordinary-coloring factor.

The three papers have distinct arguments and scopes. M2’s spectral obstruction is not inferred merely from M1, and M3’s list theorem is not obtained just by rounding a fractional coloring without further work. Keeping these distinctions makes the claimed combination more informative than a single statement that “Hadwiger is false.”

8. Sources and further reading

M1’s Theorem 1.1 and Corollary 1.2 give the connected-matching construction and Hadwiger consequences. M2’s Theorem 1.1 and Corollary 1.3 give the spectral and fractional conclusions. M3’s Theorem 1.1 is the universal list bound. Their introductions explain the different proof mechanisms and prior partial results.

The primary historical papers linked above develop the fractional, ordinary and list approaches. Wikipedia’s graph minor and fractional coloring pages are optional background for the definitions used here.

Source manuscripts

• M1. OpenAI, A counterexample to Hadwiger’s conjecture (September 23, 2026).
• M2. OpenAI, A counterexample to the Colin de Verdière chromatic conjecture (September 23, 2026).
• M3. OpenAI, A linear list-coloring bound in terms of the Hadwiger number (September 23, 2026).

Sources consulted on 11 October 2026 at repository revision fd4aeeb. Download the manuscript citations.