On the concentration of the chromatic number of random graphs
From MaRDI portal
Publication:6209746
arXiv0806.0178MaRDI QIDQ6209746FDOQ6209746
Publication date: 2 June 2008
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.
This page was built for publication: On the concentration of the chromatic number of random graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6209746)
