χ-ζ gap 3 for ω < 5 graphs

Problem 1.5 · arXiv:2408.02400

arXiv Problem high confidence— first stated 2024-08-20

Status open high confidence

Problem 1.5 asks whether for all k≥5 there exists a graph G_k with ω(G_k)<5, cochromatic number ζ(G_k)=k, and χ(G_k)=ζ(G_k)+3. The source paper establishes via Theorem 1.4 that the gap χ-ζ can reach at least 2 for graphs with ω<5 and arbitrarily large ζ, but gap 3 is left open. No follow-up resolving this specific problem was found in the indexed literature as of May 2026.

Reviewer notes. Two related 2024 papers were found and fetched: arXiv:2408.13839 ('On a question of Erdős and Gimbel on the cochromatic number') addresses a different Erdős–Gimbel question about random graphs; arXiv:2409.17614 ('The difference between the chromatic and the cochromatic number of a random graph') proves χ-ζ→∞ whp for G_{n,1/2} for ~95% of n. Neither addresses Problem 1.5 (bounded clique number, deterministic graph construction, gap exactly 3). No follow-up found in 5 web calls.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Problem. Let $k\geq 5$. Is there a graph $G_{k}$ with $\omega(G_{k})<5$, $\zeta(G_{k})=k$ and $\chi(G_{k})=\zeta(G_{k})+3$?

Context

After disproving Conjecture 1.2, the authors ask whether the gap $\chi(G)-\zeta(G)$ can reach $3$ for graphs with $\omega(G)<5$ and arbitrarily large cochromatic number $\zeta(G)$. Theorem 1.4 guarantees such graphs exist with gap at least $2$ for all large $k$, but gap $3$ remains open.

Source paper

On the difference between the chromatic and cochromatic number
Raphael Steiner · 2024-08-20
https://arxiv.org/abs/2408.02400