The concentration of the chromatic number of random graphs (Q1280244): Difference between revisions

It is proved that for every \(\delta > 0\) the chromatic number of the random graph \(G(n,p)\) with \(p=n^{-1/2-\delta}\) is asymptotically almost surely concentrated in two consecutive values. This implies that for any \(\beta < 1/2\) and any integer-valued function \(r(n) \leq O(n^{\beta})\) there exists a function \(p(n)\) such that the chromatic number of \(G(n,p(n))\) is equal to \(r(n)\) almost surely.