A note on the chromatic number of a dense random graph

Let Gn,pGn,p denote the random graph on nn labeled vertices, where each edge is included with probability pp independent of the others. We show that for all constant ppχ(Gn,p)≥n2log11−pn−2log11−plog11−pn−2log11−p2+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 χ(Gn,p)≥nα(Gn,p), where αα denotes the independence number, is not tight.