pith. sign in

arxiv: 1108.1746 · v1 · pith:DSEYRSG3new · submitted 2011-08-08 · 🧮 math.CO

The chromatic thresholds of graphs

classification 🧮 math.CO
keywords graphchromaticdeltaeverygraphsthresholdanswerscharacterise
0
0 comments X
read the original 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|G| satisfies chi(G)<C. We prove that delta_chi(H) \in {(r-3)/(r-2), (2r-5)/(2r-3), (r-2)/(r-1)} for every graph H with chi(H)=r>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\H{o}s and Simonovits [Discrete Math. 5 (1973), 323-334], and confirms a conjecture of {\L}uczak and Thomass\'e [preprint (2010), 18pp].

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.