{"id":"arxiv/2608.18620","url":"https://arxiv.org/abs/2608.18620","tags":["math.CO"],"score":0,"title":"Superlinear separation between linear and centered colorings","domain":"math.CO","source":"arxiv","authors":["Jędrzej Hodor","Piotr Micek"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-19","reactions":{}}