Chromatic thresholds in sparse random graphs1. Issue 2 (7th May 2017)

• Record Type: Journal Article
• Authors: Allen, Peter; Böttcher, Julia; Griffiths, Simon; Kohayakawa, Yoshiharu; Morris, Robert
• Is Part Of: Random structures & algorithms. Volume 51:Issue 2(2017)
• Page Start: 215
• Page End: 236
• Publication Date: 2017-05-07
• Subjects: random graphs -- chromatic threshold -- minimum degree; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20709
• Languages: English
• ISSNs: 1042-9832

Abstract

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 δ χ ( H ) : = δ χ ( H, 1 ) was initiated in 1973 by Erdős and Simonovits. Recently δ χ ( H ) was determined for all graphs H . It is known that δ χ ( H, p ) = δ χ ( H ) for all fixed p ∈ ( 0, 1 ), but that typically δ χ ( H, p ) ≠ δ χ ( H ) if p = o ( 1 ) Here we study the problem for sparse random graphs. We determine δ χ ( H, p ) for most functions p = p ( n ) when H ∈ { K 3, C 5 }, and also for all graphs H with χ ( H ) ∈ { 3, 4 } © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 215–236, 2017