Id: arxiv/2608.00691 Url: https://arxiv.org/abs/2608.00691 Tags: math.CO Score: 0 Title: Odd-Cycle Span Defect: A Polynomial Lower Bound and a Square-Root Upper Bound Domain: math.CO Source: arxiv Authors: Shuyan Chen Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-01 Page: https://delphi.science/r/arxiv/2608.00691 For a graph $G$, let $ψ(G)=\max\{χ(G[V(C)]):C$ is an odd cycle of $G\}$, with $ψ(G)=0$ when $G$ is bipartite. For positive integers $N$, set $F(N)=\max\{χ(G)-ψ(G):|V(G)|\le N\}$. The function $F$ measures the finite-order additive gap arising from an open problem of Erdos and Hajnal. We prove $N^{1/6-o(1)}\le F(N)<\sqrt{6N}$. The lower bound raises the finite-order scale supplied by the Cameron-Clow path-colour construction from $\log N/\log\log N$ to a fixed power of $N$. Its proof constructs a palette-code graph from a binary covering code $\mathcal{C}\subseteq\{0,1\}^p$ and establishes…