OPEN - $1000 The cochromatic number of$G$, denoted by$\zeta(G)$, is the minimum number of colours needed to colour the vertices of$G$such that each colour class induces either a complete graph or empty graph. Let$\chi(G)$denote the chromatic number. If$G$is a random graph with$n$vertices and each edge included independently with probability$1/2$then is it true that almost surely $\chi(G) - \zeta(G) \to \infty$ as$n\to \infty$? A problem of Erdős and Gimbel (see also [Gi16]). At a conference on random graphs in Poznan, Poland (most likely in 1989) Erdős offered \$100 for a proof that this is true, and \$1000 for a proof that this is false (although later told Gimbel that \$1000 was perhaps too much).

It is known that almost surely $\frac{n}{2\log_2n}\leq \zeta(G)\leq \chi(G)\leq (1+o(1))\frac{n}{2\log_2n}.$ (The final upper bound is due to Bollobás [Bo88]. The first inequality follows from the fact that almost surely $G$ has clique number and independence number $< 2\log_2n$.)

Heckel [He24] and, independently, Steiner [St24b] have shown that it is not the case that $\chi(G)-\zeta(G)$ is bounded with high probability, and in fact if $\chi(G)-\zeta(G) \leq f(n)$ with high probability then $f(n)\geq n^{1/2-o(1)}$ along an infinite sequence of $n$. Heckel conjectures that, with high probability, $\chi(G)-\zeta(G) \asymp \frac{n}{(\log n)^3}.$

Additional thanks to: John Gimbel and Zach Hunter