Chromatic thresholds in sparse random graphs
Allen, P.
, Böttcher, J.
, Griffiths, S., Kohayakawa, Y. & Morris, R.
(2017).
Chromatic thresholds in sparse random graphs.
Random Structures and Algorithms,
51(2), 215-236.
https://doi.org/10.1002/rsa.20709
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\H{o}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)∉{3,4}.
| Item Type | Article |
|---|---|
| Copyright holders | © 2016 Wiley Periodicals, Inc. |
| Departments | LSE > Academic Departments > Mathematics |
| DOI | 10.1002/rsa.20709 |
| Date Deposited | 22 Jun 2016 |
| Acceptance Date | 13 Apr 2016 |
| URI | https://researchonline.lse.ac.uk/id/eprint/66978 |
Explore Further
- http://www.lse.ac.uk/Mathematics/people/Julia-Boettcher.aspx (Author)
- https://www.scopus.com/pages/publications/85019018504 (Scopus publication)
- http://onlinelibrary.wiley.com/journal/10.1002/(IS... (Official URL)
ORCID: https://orcid.org/0000-0001-6555-3501
ORCID: https://orcid.org/0000-0002-4104-3635