Logo
All Random Solved Random Open
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).
Additional thanks to: John Gimbel