Author
Scott, A
Last updated
2021-11-12T02:29:04.05+00:00
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.
Symplectic ID
1136539
Download URL
http://arxiv.org/abs/0806.0178v2
Favourite
Off
Publication type
Journal Article
Publication date
02 Jun 2008
Please contact us with feedback and comments about this page.