Abstract
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) |
---|---|
Pages (from-to) | 1335-1351 |
Number of pages | 17 |
Journal | Annals of Mathematics |
Volume | 162 |
Issue number | 3 |
DOIs | |
State | Published - 2005 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Mathematics (miscellaneous)