Two values of the chromatic number of a sparse random graph

Abstract

The famous results of \L uczak (1991) and Alon -- Krivelevich (1997) state that the chromatic number $\chi(G(n,p))$ of the binomial random graph $G(n,p)$ is concentrated in two consecutive values with probability tending to 1 provided $p=p(n)\le n^{-1/2-\varepsilon}$. Unfortunately, their proofs do not give the explicit values of $\chi(G(n,p))$ as functions of $n$ and $p$. Achlioptas and Naor (2005) found these values in the sparse case when $np$ is fixed. Coja--Oghlan, Panagiotou and Steger (2008) showed that the chromatic number of $G(n,p)$ is concentrated in three explicit consecutive values provided $p=p(n)\le n^{-3/4-\delta}$, they also established a 2-point concentration for the ``half'' of the values of the parameter $p$ under these conditions. In the current paper we improve the discussed result and show that the concentration of the chromatic number in two explicit consecutive values holds ``almost everywhere'' provided $p=p(n)\le n^{-3/4-\delta}$ and $np\to+\infty$. Namely, if $r_p=\min\{r:(n-1)p<2r\ln r\}$ then we prove that for$$ (n-1)p\in\left(2(r_p-1)\ln (r_p-1),2r_p\ln r_p-\ln r_p-2-r_{p}^{-1/6}\right),$$it holds that$$  {\sf Pr}\left(\chi(G(n,p))\in\{r_p,r_p+1\}\right)\to 1\mbox{ as }n\to+\infty.$$