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
United States

Assaf Naor

Microsoft Research
Redmond, WA 98052
United States