The chromatic number of dense random graphs

Author: 

Heckel, A

Publication Date: 

August 2018

Journal: 

RANDOM STRUCTURES & ALGORITHMS

Last Updated: 

2019-04-26T05:15:25.047+01:00

Issue: 

1

Volume: 

53

DOI: 

10.1002/rsa.20757

page: 

140-182

abstract: 

© 2018 Wiley Periodicals, Inc. The chromatic number X(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 X(G). Despite several improvements of this result, the exact value of X(G) remains open. In this paper, new upper and lower bounds for X(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/X(G) of G ~G(n,p) to an explicit interval of length o(1), answering a question of Kang and McDiarmid.

Symplectic id: 

708186

Download URL: 

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article