GPT-5.6 Sol Pro Finds a Near-Quadratic Separation Between Linear and Centered Colorings

In a preprint first uploaded on August 19, 2026, Jędrzej Hodor and Piotr Micek construct graphs for which the centered chromatic number is almost quadratically larger than the linear chromatic number. More precisely, they give graphs $G_k$ with $\chi_{\mathrm{lin}}(G_k)\leq x_k$ and

$$\chi_{\mathrm{cen}}(G_k)\geq \left(\frac12-o(1)\right)\frac{x_k^2}{\log x_k}.$$

Consequently, any universal nondecreasing bound $\chi_{\mathrm{cen}}(G)\leq f(\chi_{\mathrm{lin}}(G))$ must satisfy $f(k)=\Omega(k^2/\log k)$.

The construction disproves the conjecture of Kun and coauthors that $\chi_{\mathrm{cen}}(G)\leq2\chi_{\mathrm{lin}}(G)$ for every graph. The examples are chordal, where a quadratic upper bound is already known, so the lower bound is tight up to a logarithmic factor for that class. The general upper bound quoted by the paper remains much larger, at roughly the tenth power up to logarithmic factors.

Hodor and Micek state that OpenAI's GPT-5.6 Sol Pro found the construction. They take responsibility for the correctness of the presented arguments.