On the concentration of the chromatic number of random graphs
arXiv:0806.0178
Abstract
Let 0<p<1 be fixed. Shamir and Spencer proved in the 1980s that the chromatic number of a random graph in G(n,p) is concentrated in an interval of length about n^{1/2}. In this explanatory note, we give a proof of a result due due Noga Alon, showing that the chromatic number is concentrated in an interval of length about n^{1/2}/log n.