On the chromatic number of random graphs

In this paper we consider the classical Erdős–Rényi model of random graphs G n , p . We show that for p = p ( n ) ⩽ n − 3 / 4 − δ , for any fixed δ > 0 , the chromatic number χ ( G n , p ) is a.a.s. ℓ, ℓ + 1 , or ℓ + 2 , where ℓ is the maximum integer satisfying 2 ( ℓ − 1 ) log ( ℓ − 1 ) ⩽ p ( n − 1 ) .