Chromatic Thresholds in Sparse Random Graphs

The chromatic threshold delta(chi) (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 subset of G(n, p) with minimum degree delta(G) >= dpn has bounded chromatic number. The study of d. (H) := delta(chi) (H, 1) was initiated in 1973 by Erdos and Simonovits. Recently delta(chi) (H) was determined for all graphs H. It is known that delta(chi) (H, p) =delta(chi) (H) for all fixed p epsilon (0, 1), but that typically delta(chi) (H, p) epsilon not equal delta(chi) (H) if p = 0(1). Here we study the problem for sparse random graphs. We determine delta(chi) (H, p) for most functions p = p(n) when H. {K3, C5}, and also for all graphs H with x(H) is not an element of {3, 4}. (C) 2017 Wiley Periodicals, Inc.