The chromatic number of very dense random graphs

The chromatic number of a very dense random graph $G(n,p)$, with $p\ge 1-n^{-c}$ for some constant $c>0$, was first studied by Surya and Warnke, who conjectured that the typical deviation of $\chi (G(n,p))$ from its mean is of order $\sqrt{{\mu }_r}$, where ${\mu }_r$ is the expected number of independent sets of size $r$, and $r$ is maximal such that ${\mu }_r>1$, except when ${\mu }_r=O(\log n)$. They moreover proved their conjecture in the case $n^{-2}\ll 1-p=O(n^{-1})$. In this paper, we study $\chi (G(n,p))$ in the range $n^{-1}\log n\ll 1-p\ll n^{-2\mathrm{/}3}$, that is, when the largest independent set of $G(n,p)$ is typically of size 3. We prove in this case that $\chi (G(n,p))$ is concentrated on some interval of length $O(\sqrt{{\mu }_3})$, and for sufficiently `smooth’ functions $p=p(n)$, that there are infinitely many values of $n$ such that $\chi (G(n,p))$ is not concentrated on any interval of size $o(\sqrt{{\mu }_3})$. We also show that $\chi (G(n,p))$ satisfies a central limit theorem in the range $n^{-1}\log n\ll 1-p\ll n^{-7\mathrm{/}9}$.