The Chromatic Number of Random Graphs for Most Average Degrees
Amin Coja‐Oghlan, Dan Vilenchik · International Mathematics Research Notices · 2015
For a fixed number |$d>0$| and |$n$| large, let |$G(n,d/n)$| be the random graph on |$n$| vertices in which any two vertices are connected with probability |$d/n$| independently. The problem of determining the chromatic number of |$G(n,d/n)$| goes back to the famous 1960 article of Erdös and Rényi that started the theory of random graphs [Magayar Tud. Akad. Mat. Kutato Int. Kozl. 5 (1960) 17–61]. Progress culminated in the landmark paper of Achlioptas and Naor [Ann. Math. 162 (2005) 1333–1349], in which they calculate the chromatic number precisely for all |$d$| in a set |$S\subset (0,\infty )$| of asymptotic density |$\lim _{z\rightarrow \infty }\frac 1z\int _0^z\textbf {1}_S=\frac {1}{2}$|, and up to an additive error of one for the remaining |$d$|. Here we obtain a near-complete answer by determining the chromatic number of |$G(n,d/n)$| for all |$d$| in a set of asymptotic density 1.