Conjecture on the chromatic–cochromatic gap in random graphs

Let $G$ be sampled from the binomial random graph model $G_{n,1/2}$, and let $u$ denote the chromatic number of $G$ and $\bar\chi$ its cochromatic number, so that the gap is $\nu-\bar\chi$. Here, $f(n)=\Theta(n/\log^3 n)$ means that there are positive constants bounding the ratio between the gap and $n/\log^3 n$ for all sufficiently large $n$. Chromatic–cochromatic gap conjecture. With high probability,

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

The conjecture predicts the asymptotically sharp order of the difference between the chromatic and cochromatic numbers of a random graph. The paper proves a weaker lower bound of $n^{1-\varepsilon}$ for roughly $95\%$ of values of $n$ and conjectures that the stated order holds for all $n$.