Chromatic thresholds in dense random graphs

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.



The Research, Innovation and Dissemination Center for Neuromathematics is hosted by the University of São Paulo and funded by FAPESP (São Paulo Research Foundation).


User login



1010 Matão Street - Cidade Universitária - São Paulo - SP - Brasil. 05508-090. See map.

55 11 3091-1717

General contact email:

Media inquiries email: