| Full text | |
| Author(s): |
Allen, Peter
[1]
;
Boettcher, Julia
[1]
;
Griffiths, Simon
[2]
;
Kohayakawa, Yoshiharu
[1]
;
Morris, Robert
[2]
Total Authors: 5
|
| Affiliation: | [1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[2] IMPA, Rio De Janeiro, RJ - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | ADVANCES IN MATHEMATICS; v. 235, p. 261-295, MAR 1 2013. |
| Web of Science Citations: | 12 |
| Abstract | |
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. (AU) | |
| FAPESP's process: | 09/17831-7 - Embedding and packing problems in extremal graph theory |
| Grantee: | Julia Boettcher |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 10/09555-7 - Embedding, randomised and structural problems in extremal graph theory |
| Grantee: | Peter David Allen |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |