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

Abstract

Given $d \in (0,\infty)$ let $k_d$ be the smallest integer $k$ such that $d\lt 2k\log k$. We prove that the chromatic number of a random graph $G(n,d/n)$ is either $k_d$ or $k_d+1$ almost surely.

Authors

Dimitris Achlioptas

Microsoft Research, Redmond, WA 98052

Assaf Naor

Princeton University, Princeton, NJ 08544