arXiv:0806.0178 Abstract | arXiv Analytics

arXiv:0806.0178 [math.CO]Abstract References Reviews Resources

On the concentration of the chromatic number of random graphs

Published 2008-06-02, updated 2017-10-18Version 2

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.

Categories: math.CO

Subjects: 05C15, 05C80

Keywords: chromatic number, random graph, concentration

Related articles: Most relevant | Search more

arXiv:math/0506167 [math.CO] (Published 2005-06-09)

Bounds for the $b$-chromatic number of some families of graphs

Mekkia Kouider, Manouchehr Zaker

arXiv:math/0208072 [math.CO] (Published 2002-08-09, updated 2003-11-24)

Topological lower bounds for the chromatic number: A hierarchy

Jiri Matousek, Günter M. Ziegler

arXiv:1404.1698 [math.CO] (Published 2014-04-07, updated 2014-09-20)

The Sum and Product of Chromatic Numbers of Graphs and their Line Graphs