The chromatic number of dense random graphs. Issue 1 (24th January 2018) - Heckel, Annika
Abstract: The chromatic number χ ( G ) of a graph G is defined as the minimum number of colors required for a vertex coloring where no two adjacent vertices are colored the same. The chromatic number of the dense random graph G ∼ G ( n, p ) where p   ∈   ( 0, 1 ) is constant has been intensively studied since the 1970s, and a landmark result by Bollobás in 1987 first established the asymptotic value of χ ( G ) . Despite several improvements of this result, the exact value of χ ( G ) remains open. In this paper, new upper and lower bounds for χ ( G ) are established. These bounds are the first ones that match each other up to a term of size o (1) in the denominator: they narrow down the coloring rate n / χ ( G ) of G   ∼   G ( n, p ) to an explicit interval of length o (1), answering a question of Kang and McDiarmid.