Chromatic thresholds in dense random graphs
Apr 23, 2018
Peter Allen, Julia Böttcher, Simon Griffiths, Yoshiharu Kohayakawa and Robert Morris
The chromatic threshold δχ(H, p) of a graph H with respect to the random graphG(n, p) is the infimum over d > 0 such that the following holds with high probability: the familyof H-free graphs G ⊆ G(n, p) with minimum degree δ(G) ≥ dpn has bounded chromatic number.The study of the parameter δχ(H) := δχ(H,1) was initiated in 1973 by Erd˝os and Simonovits, andwas recently determined for all graphs H. In this paper we show that δχ(H, p) = δχ(H) for all fixedp ∈ (0, 1), but that typically δχ(H, p) ≠ δχ(H) if p = o(1). We also make significant progress towardsdetermining δχ(H, p) for all graphs H in the range p = n−o(1). In sparser random graphs the problem issomewhat more complicated, and is studied in a separate paper.
The whole paper is available here.
Share on Facebook
