| Texto completo | |
| Autor(es): |
Allen, Peter
;
Bottcher, Julia
;
Griffiths, Simon
;
Kohayakawa, Yoshiharu
;
Morris, Robert
Número total de Autores: 5
|
| Tipo de documento: | Artigo Científico |
| Fonte: | RANDOM STRUCTURES & ALGORITHMS; v. 51, n. 2, p. 185-214, SEP 2017. |
| Citações Web of Science: | 0 |
| Resumo | |
The chromatic threshold delta(chi) (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 subset of G(n, p) with minimum degree delta(G) >= dpn has bounded chromatic number. The study of the parameter delta(chi) (H) := delta(chi) (H, 1) was initiated in 1973 by Erdos and Simonovits, and was recently determined for all graphs H. In this paper we show that delta(chi) (H, p) = delta(chi) (H) for all fixed p epsilon (0, 1), but that typically delta(chi) (H, p) not equal delta(chi) (H) if p = 0(1). We also make significant progress towards determining delta(chi) (H, p) for all graphs H in the range p = n(-0(1)). In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper. (C) 2017 Wiley Periodicals, Inc. (AU) | |
| Processo FAPESP: | 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação |
| Beneficiário: | Carlos Eduardo Ferreira |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| 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 |
| Processo FAPESP: | 13/07699-0 - Centro de Pesquisa, Inovação e Difusão em Neuromatemática - NeuroMat |
| Beneficiário: | Oswaldo Baffa Filho |
| Modalidade de apoio: | Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs |