2026/08/01 by Shuyan Chen
Mathematics · #math.CO #msc:05C15 #msc:05C35 #msc:05C38 #msc:94B75
arxiv created 2026/08/01 · arxiv updated 2026/08/04
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)|≤ N\. The function F measures the finite-order additive gap arising from an open problem of Erdos and Hajnal. We prove N1/6-o(1)≤ F(N)<√(6N). The lower bound raises the finite-order scale supplied by the Cameron-Clow path-colour construction from log N/loglog N to a fixed power of N. Its proof constructs a palette-code graph from a binary covering code C⊆\0,1\p and establishes the exact identities χ(G)=2p+ℓ-ρ(C) and ψ(G)=2p. Near-middle Hamming coverings yield the exponent 1/6. The upper bound combines Polavarapu's connectivity theorem, the Chvatal-Erdos Hamiltonicity theorem, and maximum-independent-set stripping.