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 -