Chromatic thresholds in sparse random graphs

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