The chromatic thresholds of graphs
By Peter Allen, Julia Bottcher, Simon Griffiths, Yoshiharu Kohayakawa, Robert Morris. 2011
48 citations recorded by the source corpus.
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|G| satisfies chi(G) 2. We moreover characterise the graphs H with a given chromatic threshold, and thus determine delta_chi(H) for every graph H. This answers a question of Erdős and Simonovits [Discrete Math. 5 (1973), 323-334], and confirms a conjecture of Łuczak and Thomasse [preprint (2010), 18pp].
Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/a0248cf9a3320b77c5f3241991446a5f205bc742
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
- Wojciech Samotij
- David Conlon
- Mathias Schacht
- William T. Gowers
- Peter Keevash
- A. Sah
- Robert Morris
- Dhruv Mubayi
In Discrete Mathematics and Combinatorics
- Wojciech Samotij
- David Conlon
- Mathias Schacht
- William T. Gowers
- A. Sah
- Peter Keevash
- Robert Morris
- Terence Tao
In Geometry and Topology
- David Conlon
- Wojciech Samotij
- Mathias Schacht
- William T. Gowers
- A. Sah
- Peter Keevash
- Robert Morris
- Terence Tao
Citations in the corpus
- On the KŁR conjecture in random graphs (2013, background): “For further discussion and related results, we refer the reader to [9, 43].”