| Texto completo | |
| Autor(es): |
Allen, Peter
[1]
;
Boettcher, Julia
[1]
;
Griffiths, Simon
[2]
;
Kohayakawa, Yoshiharu
[1]
;
Morris, Robert
[2]
Número total de Autores: 5
|
| Afiliação do(s) autor(es): | [1] Univ Sao Paulo, Inst Matemat & Estat, BR-05508090 Sao Paulo - Brazil
[2] IMPA, Rio De Janeiro, RJ - Brazil
Número total de Afiliações: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | ADVANCES IN MATHEMATICS; v. 235, p. 261-295, MAR 1 2013. |
| Citações Web of Science: | 12 |
| Resumo | |
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) | |
| Processo FAPESP: | 09/17831-7 - Problemas de imersão e empacotamento em teoria extremal dos grafos |
| Beneficiário: | Julia Boettcher |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |
| Processo FAPESP: | 10/09555-7 - Problemas estruturais, probabilísticos e de imersão em teoria extremal dos grafos |
| Beneficiário: | Peter David Allen |
| Modalidade de apoio: | Bolsas no Brasil - Pós-Doutorado |