Bollobás [Bo88] proved that $\chi(G) \sim \frac{n}{2\log_2n}$ with high probability.

Shamir and Spencer [ShSp87] proved that, for any function $\omega(n)$ such that $\omega(n)/\sqrt{n}\to \infty$, there is a function $f(n)$ such that\[\mathbb{P}(\lvert\chi(G)-f(n)\rvert<\omega(n))\to 1\]as $n\to \infty$. This is proved with $\omega(n)\frac{\log n}{\sqrt{n}}\to \infty$ in Exercise 3 of Section 7.9 of Alon and Spencer [AlSp16] (a proof is also given by Scott [Sc17]).

Heckel [He21] proved that if $f$ and $\omega$ are such that\[\mathbb{P}(\lvert\chi(G)-f(n)\rvert<\omega(n))\to 1\]as $n\to \infty$ then, for any $c<1/4$, there are infinitely many $n$ such that $\omega(n)>n^c$. This was improved to any $c<1/2$ by Heckel and Riordan [HeRi23].

View the LaTeX source

This page was last edited 27 January 2026.