Graph theory seminar - Jim Geelen

Structure in Dense Triangle-free Graphs Part 1

Abstract:

Brandt and Thomass\’ e proved that every $n$-vertex triangle-free graph with minimum degree greater than $\frac 1 3 n$ is $4$-colourable. On the other hand, Hijnal proved that, for each $\epsilon>0$, there are triangle-free graphs with minimum degree greater than $(\frac 1 3 - \epsilon)n$ that have arbitrarily large chromatic number. The proof of Brandt and Thomass\’ e’s result is quite hard, but there are a number of related results with very nice proofs that I will explain.
None of the results or proofs that I will present are original.