A note on the chromatic number of a dense random graph

Let G n , p denote the random graph on n labeled vertices, where each edge is included with probability p independent of the others. We show that for all constant p χ ( G n , p ) ≥ n 2 log 1 1 − p n − 2 log 1 1 − p log 1 1 − p n − 2 log 1 1 − p 2 + o ( 1 ) holds with high probability. This improves the best known lower bound for the chromatic number of dense random graphs and shows in particular that the estimate χ ( G n , p ) ≥ n α ( G n , p ) , where α denotes the independence number, is not tight.