We prove that for every constant δ > 0 the chromatic number of the random graph G(n,p) with p = n-1/2-δ is asymptotically almost surely concentrated in two consecutive values. This implies that for any β < 1/2 and any integer valued function r(n)≤O(nβ) there exists a function p(n) such that the chromatic number of G(n,p(n)) is precisely r(n) asymptotically almost surely.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics