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 $χ_{\mathrm{cen}}(G)$ and $χ_{\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 $χ_{\mathrm{cen}}(G) \leq f(χ_{\mathrm{lin}}(G))$ for every graph $G$, then $f(k) = Ω(k^2 / \log k)$. The construction was found by OpenAI's GPT-5.6 Sol Pro.

Disclosure

“χcen (G) = O(χlin (G)2 ) for all chordal graphs G. Thus, we obtain an almost tight bound on the optimal binding function for this class. Statement of AI use The construction was found by OpenAI’s GPT-5.6 Sol Pro. The authors take responsibility for the mathematical correctness of the presented arguments. References [1] Prosenjit Bose, Vida Dujmović, Hussein Houdrouge, Mehrnoosh Javarsineh, an”

PDF page 4

Classification

Substantial mathematical content or result generation

Multiplier

10

Verified

2026-08-22T17:02:44.112097Z

Structural counts