Superlinear separation between linear and centered colorings

Abstract

A vertex-coloring of a graph is centered if every connected subgraph has a vertex with a unique color. A vertex-coloring of a graph is linear if every path in the graph has a vertex with a unique color. Let ${\chi }_{\mathrm{cen}}(G)$ and ${\chi }_{\mathrm{lin}}(G)$ be the minimum number of colors in a centered (resp. linear) coloring of $G$. We present a family of graphs witnessing that if $f$ is a nondecreasing function such that ${\chi }_{\mathrm{cen}}(G)\le f({\chi }_{\mathrm{lin}}(G))$ for every graph $G$, then $f(k)=\Omega (k^2/\log k)$. The construction was found by OpenAI's GPT-5.6 Sol Pro.

4 pages