2015/08/16 by Peter J. Allen, Julia Böttcher, Allen, Peter +7
Computer Science · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1508.03875
openalex publication_date 2015/08/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) ≥ dpn 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∈\K3,C5\, and also for all graphs H with χ(H) \not∈ \3,4\.