Chromatic thresholds in sparse random graphs |
| |
| Authors: | Peter Allen Julia Böttcher Simon Griffiths Yoshiharu Kohayakawa Robert Morris |
| |
| Institution: | 1. Department of Mathematics, London School of Economics, London, UK;2. Department of Statistics, University of Oxford, Oxford, UK;3. Instituto de Matemática e Estatística, Universidade de S?o Paulo, S?o Paulo, Brazil;4. IMPA, Rio de Janeiro, RJ, Brazil |
| |
| Abstract: | The chromatic threshold  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  with minimum degree  has bounded chromatic number. The study of  was initiated in 1973 by Erd?s and Simonovits. Recently  was determined for all graphs H . It is known that  for all fixed  , but that typically  if  Here we study the problem for sparse random graphs. We determine  for most functions  when  , and also for all graphs H with  © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 215–236, 2017 |
| |
| Keywords: | random graphs chromatic threshold minimum degree |
|
|
