Erdős #762 — is χ(G)≤ζ(G)+2 when ω(G)<5 and ζ(G)≥4? (Erdős–Gimbel–Straight 1988)

Statement

The cochromatic number $\zeta(G)$ of a graph $G$ is the minimum number of colours needed to colour $V(G)$ so that every colour class induces either a complete graph (a clique) or an empty graph (an independent set) — i.e. the minimum size of a partition of $V(G)$ into *homogeneous* sets. Always $\zeta(G)\le\chi(G)$ (an ordinary proper colouring is in particular a homogeneous-class colouring).

Conjecture (Erdős, Gimbel, Straight, 1988 [EGS90]). Every graph $G$ with $\omega(G)<5$ (i.e. $K_5$-free) and $\zeta(G)\ge 4$ satisfies $$\chi(G)\le\zeta(G)+2.$$

Erdős, Gimbel and Straight had already proved the general fact that for every $n>2$ there is a finite $f(n)$ such that every $K_n$-free graph $G\ne K_{n-1}$ satisfies $\chi(G)\le\zeta(G)+f(n)$, with $f(3)=0$, $f(4)=1$ exactly, and $f(n)$ growing at least linearly (in fact they showed $f(n)\ge 3(n-3)/2$ for odd $n$). They found several $K_5$-free examples with $\chi(G)>\zeta(G)+2$ showing $f(5)\ge 3$, but every such example they could construct had $\zeta(G)\le 3$; unable to find one with $\zeta(G)>3$, they conjectured the bound $\chi\le\zeta+2$ was simply *forced* once $\zeta\ge 4$ — i.e. that $f(5)=3$ is achieved only in the "small-$\zeta$" regime and the gap closes back to $2$ for larger cochromatic number.

Facts

- Status: SOLVED, in the negative (disproved). Marked "DISPROVED (LEAN)" on erdosproblems.com/762 — solved and the disproof formally verified in Lean (fetched 2026-07-02); exact source file in the google-deepmind/formal-conjectures Lean statement bank not independently located in this pass (see provenance). - Origin: P. Erdős, J. Gimbel, H. J. Straight, "Chromatic number versus cochromatic number in graphs with bounded clique number," *European J. Combin.* 11(3) (1990), 235–240 [EGS90] (the paper itself is dated/labelled 1988 by Steiner and by erdosproblems.com, published 1990). Repeated by Erdős and Gimbel in "Some problems and results in cochromatic theory," *Annals of Discrete Mathematics* 55 (1993), 261–264, and by Jensen & Toft, *Graph Coloring Problems* (1995), Problem 17.3. - A closely related finiteness question was open alongside it: Erdős and Gimbel (1993) reported constructing "several hundred" $K_5$-free graphs $G$ with $\chi(G)>\zeta(G)+2$ but suspected there might be only *finitely* many. This is answered — also negatively — by the same paper that disproves the conjecture. - Disproof: Raphael Steiner, "On the difference between the chromatic and cochromatic number," arXiv:2408.02400 (Aug 2024). Main theorem (Thm 1.4): *there are infinitely many graphs $G$ with $\omega(G)<5$, $\zeta(G)=4$, and $\chi(G)=7$* — violating $\chi\le\zeta+2=6$ by exactly $1$, and simultaneously refuting the "finitely many" hope. - Partial positive result predating the disproof: Liu, Chen, Ou (2006) had proved the conjecture *for a restricted class of line graphs* — i.e. it was known to hold on that subfamily even though it is now known false in general. - What remains open after the disproof (both posed in the same Steiner paper, and both listed as open on erdosproblems.com as of this fetch): - *Problem 1.5 (Steiner 2024).* For $k\ge5$, is there a graph $G_k$ with $\omega(G_k)<5$, $\zeta(G_k)=k$, and $\chi(G_k)=\zeta(G_k)+3$? (I.e. does the gap-$3$ phenomenon persist, or even grow, as $\zeta$ itself grows, rather than only at $\zeta=4$?) - The precise value of $f(5)$ (and $f(n)$ for $n\ge5$ generally) is still unknown, though Steiner's Proposition 1.1 shows $f(n)$ is in principle computable by a finite search once $n$ is fixed (via a Ramsey-number-based bound on the size of a minimum counterexample) — turning "find $f(5)$" from an open-ended question into a (currently infeasible-scale, but finite) computation. - Sibling problem, same 1993 Erdős–Gimbel paper, same disproof paper: whether $\chi(G_{n,1/2})-\zeta(G_{n,1/2})\to\infty$ almost surely for the Erdős–Rényi random graph — Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)?, still open (Erdős's own \$1000 problem). Steiner's paper proves a *positive-probability* $\Omega(n^{1/2-\epsilon})$ gap for infinitely many $n$ via the same Harris–FKG machinery used elsewhere in that paper, but the full almost-sure statement remains unresolved; #762's construction is logically independent of that random-graph argument (different section of the same paper, different technique).

Solution

Answer: NO — the conjecture is false. Steiner (arXiv:2408.02400, Thm 1.4) exhibits infinitely many graphs $G$ with $\omega(G)<5$, $\zeta(G)=4$, $\chi(G)=7>\zeta(G)+2=6$.

The transferable technique — a "Ramsey-unavoidable witness core, then attach one pendant twin per witness set" gadget (a generalized Mycielski-style blow-up).

1. Build a small "forcing core" $H$ with an unavoidability property. Steiner constructs $H$ on just $11$ vertices: take two disjoint $5$-cycles $C_1,C_2$, add *all* edges between $C_1$ and $C_2$ (a complete join), then add one further vertex $v$ adjacent to a single chosen vertex $x_1\in C_1$ and $x_2\in C_2$ only. Three facts about $H$ drive everything: - $\omega(H)<5$: $C_1,C_2$ are triangle-free, so the join has clique number $4$ (one edge from each side plus... concretely $\omega(H-v)=4$), and $v$ has degree $2$ so cannot enlarge any clique to $5$. - $V(H)$ splits into $3$ cliques (so $\zeta(H)\le3$): $\{v,x_1,x_2\}$ is a triangle, and $C_1-x_1$, $C_2-x_2$ (each a path on $4$ vertices) each split into $2$-edge matchings, i.e. two size-$4$ cliques — wait, concretely each is partitioned so that $H$ decomposes into $3$ homogeneous (clique) classes total. - The unavoidability lemma (the real engine, Lemma 3.1(3)): *every* proper $6$-colouring of $H$ contains a subset $X\subseteq V(H)$ with $\omega(H[X])<4$ that is rainbow — uses all $6$ colours. This is proved via a short case analysis (Observation 3.2) on how a proper $3$-colouring of a $5$-cycle must distribute its $3$ colours: because $C_1$ and $C_2$ are fully joined, any proper $6$-colouring of $H$ must use $3$ colours entirely on $C_1$ and the other $3$ entirely on $C_2$; the $5$-cycle's rigid $3$-colouring structure then *forces* a non-adjacent pair on $C_1$ carrying (together with $v$'s colour) all of $C_1$'s $3$ colours, which combines with $3$ well-chosen vertices of $C_2$ into a $6$-vertex rainbow set of clique number $\le3$. 2. Encode every possible "witness" as a fresh pendant independent twin. Let $\mathcal X$ be the family of *all* subsets $X\subseteq V(H)$ with $\omega(H[X])<4$ (these are exactly the sets that Lemma 3.1(3) says *some* $6$-colouring will make rainbow). For every $X\in\mathcal X$, attach one or more new vertices whose neighbourhood is *exactly* $X$, all new vertices pairwise non-adjacent and disjoint across different $X$. Call the result $G$. (Since there are infinitely many ways to choose how many twin-vertices to attach per $X$, this already produces an *infinite family* of counterexamples — directly answering Problem 1.3 as well as Conjecture 1.2.) 3. Why $\omega(G)$ stays $<5$: any clique in $G$ either lives entirely in $H$ (size $\le4$) or is one twin vertex plus a clique inside its neighbourhood $X$ (size $\le1+\omega(H[X])\le1+3=4$). 4. Why $\zeta(G)$ stays exactly $4$: the $3$ cliques covering $H$ plus the one giant independent set of *all* twin vertices together is a $4$-part homogeneous partition, so $\zeta(G)\le4$. A counting argument (using $|V(H)|=11$ and $|V(G)|>12$, plus the bound "every independent set meets $V(H)$ in $\le3$ vertices, every clique has size $\le4$") rules out a $3$-part homogeneous partition, so $\zeta(G)=4$ exactly. 5. Why $\chi(G)$ jumps to $7$ — the punchline. Trivially $\chi(G)\le\chi(H)+1=7$ (colour $H$ with $6$ colours, twins with a $7$th). Suppose for contradiction $G$ had a proper $6$-colouring. Restricted to $H$ it's a proper $6$-colouring of $H$, so by the unavoidability lemma some $X\in\mathcal X$ is rainbow under it — but *every* vertex attached with neighbourhood exactly $X$ now has all $6$ colours forbidden among its neighbours, so it cannot be properly coloured at all. Contradiction. Hence $\chi(G)=7$, while $\zeta(G)+2=6$. 6. The transferable idea, stated abstractly (a generalized Mycielski/blow-up gadget): this is the same *shape* of trick as the classical Mycielski construction (which raises $\chi$ by $1$ while holding $\omega=2$, by attaching one twin vertex per original vertex plus an apex) — but generalized from "one twin per vertex" to "one twin per element of a whole combinatorially-derived family of witness sets, where the family is exactly what a Ramsey-type unavoidability lemma on a small hand-built core forces to be hit." The two-step recipe — (a) engineer a small core graph where *every* extremal-for-one-parameter colouring is provably forced to leave some structured witness set fully exposed (a pigeonhole/Ramsey argument on a rigid substructure like $C_5$'s $3$-colourings), then (b) attach a pendant twin vertex to *every* member of the resulting witness family, with neighbourhood exactly that witness set, so that leaving it exposed becomes uncolourable — is the reusable engine. It cleanly decouples the two parameters being compared ($\zeta$ controlled by the coarse clique/independent-set structure of $H$ plus twins; $\chi$ controlled by the fine unavoidability lemma) and is the kind of construction to reach for on any open problem of the shape "does bounding parameter $A$ force parameter $B$ to stay close to it" — e.g. it is the natural next tool to try on Problem 1.5 (does the gap-of-$3$ phenomenon persist for larger $\zeta$?), by hunting for an analogous small rigid core at higher $\zeta$.

Related

- Erdős #625 — does χ(G)−ζ(G)→∞ for random G(n,1/2)? — the sibling Erdős–Gimbel 1993 \$1000 question, "does $\chi(G_{n,1/2})-\zeta(G_{n,1/2})\to\infty$ almost surely?", still open; resolved in the same paper (arXiv:2408.02400) that disproves #762, via an unrelated Harris–FKG argument in a later section. - Lean 4 formalization of constructions and conditional reductions (Erdős-problem context) — the google-deepmind/formal-conjectures Lean statement-bank ecosystem; erdosproblems.com marks #762 "DISPROVED (LEAN)" (proof machine-verified), though this pass could not independently locate the specific source file. - Structural constraints on a hypothetical minimal counterexample (minimum-degree, connectivity, adjacency pruning) — Steiner's Proposition 1.1 (a Ramsey-number-based bound showing a minimum counterexample to $\chi\le\zeta+f$ has bounded size, so $f(n)$ is finitely computable for each fixed $n$) is an instance of this pattern, used here as a structural/finiteness tool distinct from the main gadget construction.