The Erdős–Gimbel cochromatic gap conjecture

Let $G$ be sampled from the binomial random graph $G_{n,1/2}$, and let $\chi(G)$ and $\zeta(G)$ denote its chromatic and cochromatic numbers, respectively. Here, “with high probability” means with probability tending to $1$ as $n\to\infty$. Erdős–Gimbel cochromatic gap conjecture. With high probability,

$$\chi(G)-\zeta(G)=\Theta(n/\log^3 n).$$

This conjecture concerns the typical difference between the chromatic and cochromatic numbers of a random graph and predicts a gap of order $n/\log^3 n$. The preceding discussion presents it as an expected consequence of first-moment heuristics; its resolution is not given in the supplied text.