×

The chromatic number of random graphs for most average degrees. (English) Zbl 1404.05189

Summary: 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 P. Erdős and A. Rényi that started the theory of random graphs [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 5, 17–61 (1960; Zbl 0103.16301)]. Progress culminated in the landmark paper of D. Achlioptas and A. Naor [Ann. Math. (2) 162, No. 3, 1335–1351 (2005; Zbl 1094.05048)], 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 {1}{z}\int_0^z\mathbf{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.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs