Structure in Dense Triangle-free Graphs Part 1
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 6486|
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.
200 University Avenue West
Waterloo, ON N2L 3G1