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.
|Original language||English (US)|
|Number of pages||17|
|Journal||Annals of Mathematics|
|State||Published - 2005|
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty