TY - JOUR
T1 - The two possible values of the chromatic number of a random graph
AU - Achlioptas, Dimitris
AU - Naor, Assaf
PY - 2005
Y1 - 2005
N2 - Given d ∈ (0, ∞) let kd be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n, d/n) is either kd or kd + 1 almost surely.
AB - Given d ∈ (0, ∞) let kd be the smallest integer k such that d < 2k log k. We prove that the chromatic number of a random graph G(n, d/n) is either kd or kd + 1 almost surely.
UR - http://www.scopus.com/inward/record.url?scp=33745880378&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33745880378&partnerID=8YFLogxK
U2 - 10.4007/annals.2005.162.1335
DO - 10.4007/annals.2005.162.1335
M3 - Article
AN - SCOPUS:33745880378
SN - 0003-486X
VL - 162
SP - 1335
EP - 1351
JO - Annals of Mathematics
JF - Annals of Mathematics
IS - 3
ER -