The chromatic thresholds of graphs

The chromatic threshold delta(chi)(H) of a graph H is the infimum of d > 0 such that there exists C = C(H, d) for which every. H-free graph G with minimum degree at least d vertical bar G vertical bar satisfies chi(G) <= C. We prove that delta(chi)(H) epsilon {r-3/r-2, 2r-5/2r-3, r-2/r-1} for every graph H with chi(H) = r >= 3. We moreover characterise the graphs H with a given chromatic threshold, and thus determine S chi(H) for every graph H. This answers a question of Erdos and Simonovits [P. Erdos, M. Simonovits, On a valence problem in extremal graph theory, Discrete Math. 5 (1973), 323-334], and confirms a conjecture of Luczak and Thomasse [Tomasz Luczak, Stephan Thomasse, Colouring dense graphs via VC-dimension, arXiv:1011.4310 (submitted for publication)]. (C) 2012 Elsevier Inc. All rights reserved.