Expose-and-merge exploration and the chromatic number of a random graph (Q1104942)

The expose-and-merge paradigm for exploring random graphs is presented. An algorithm of complexity \(n^{O(\log n)}\) is described and used to show that the chromatic number of a random graph for any edge probability \(0<p<1\) falls in the interval \[ [(\frac{1}{2}-\epsilon)\log (1/(1- p))\frac{n}{\log n},\quad (\frac{2}{3}+\epsilon)\log (1/(1- p))\frac{n}{\log n}] \] with probability approaching unity as \(n\to \infty\).