χ-ζ gap 3 for ω < 5 graphs

AX_chromatic_cochromatic_gap_three_small_clique

Source: arXiv:2408.02400 — On the difference between the chromatic and cochromatic number

Problem 1.5 · arXiv:2408.02400

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

Status ai-proved high confidence

A 13-vertex circulant-complement seed has (omega,zeta,chi)=(4,4,7), and iterated Mycielski constructions raise zeta and chi together by one while preserving clique number.

Auto-reviewed 2026-08-31 with gpt-5.6-sol.

AI-generated write-up ai-proved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

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