Graph theory seminar - Jim Geelen

Wednesday, April 2, 2014 3:30 pm - 3:30 pm EDT (GMT -04:00)

Structure in Dense Triangle-free Graphs Part 1

Speaker: Jim Geelen
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.