| Full text | |
| Author(s): |
Allen, Peter
;
Bottcher, Julia
;
Griffiths, Simon
;
Kohayakawa, Yoshiharu
;
Morris, Robert
Total Authors: 5
|
| Document type: | Journal article |
| Source: | RANDOM STRUCTURES & ALGORITHMS; v. 51, n. 2, p. 215-236, SEP 2017. |
| Web of Science Citations: | 1 |
| Abstract | |
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 d. (H) := delta(chi) (H, 1) was initiated in 1973 by Erdos and Simonovits. Recently delta(chi) (H) was determined for all graphs H. It is known that delta(chi) (H, p) =delta(chi) (H) for all fixed p epsilon (0, 1), but that typically delta(chi) (H, p) epsilon not equal delta(chi) (H) if p = 0(1). Here we study the problem for sparse random graphs. We determine delta(chi) (H, p) for most functions p = p(n) when H. [K3, C5], and also for all graphs H with x(H) is not an element of [3, 4]. (C) 2017 Wiley Periodicals, Inc. (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: | 13/07699-0 - Research, Innovation and Dissemination Center for Neuromathematics - NeuroMat |
| Grantee: | Oswaldo Baffa Filho |
| Support Opportunities: | Research Grants - Research, Innovation and Dissemination Centers - RIDC |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| 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 |