The two possible values of the chromatic number of a random graph

Abstract

For every 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. If d ∈ (2k log k - log k, 2k log k) we further prove that the chromatic number almost surely equals k+1.

Locations

• arXiv (Cornell University) - View - PDF