Chromatic thresholds in dense random graphs1. Issue 2 (16th May 2017) - Allen, Peter; Böttcher, Julia; Griffiths, Simon; Kohayakawa, Yoshiharu; Morris, Robert
Abstract: The chromatic threshold δ χ ( H, p ) of a graph H with respect to the random graph G ( n, p ) is the infimum over d  > 0 such that the following holds with high probability: the family of H ‐free graphs G ⊂ G ( n, p ) with minimum degree δ ( G ) ⩾ d p n has bounded chromatic number. The study of the parameter δ χ ( H ) : = δ χ ( H, 1 ) was initiated in 1973 by Erdős and Simonovits, and was recently determined for all graphs H . In this paper we show that δ χ ( H, p ) = δ χ ( H ) for all fixed p ∈ ( 0, 1 ), but that typically δ χ ( H, p ) ≠ δ χ ( H ) if p = o ( 1 ) . We also make significant progress towards determining δ χ ( H, p ) for all graphs H in the range p = n − o ( 1 ) . In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 185–214, 2017