The chromatic number of dense random graphs. Issue 1 (24th January 2018)

• Record Type: Journal Article
• Authors: Heckel, Annika
• Is Part Of: Random structures & algorithms. Volume 53:Issue 1(2018)
• Page Start: 140
• Page End: 182
• Publication Date: 2018-01-24
• Subjects: chromatic number -- graph coloring -- random graphs -- second moment method; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20757
• Languages: English
• ISSNs: 1042-9832

Abstract

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.