Graph theory seminar - Jim Geelen

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

Structure in Dense Triangle-free Graphs - Part 2

Speaker: Jim Geelen
Affiliation: University of Waterloo
Room: Mathematics and Computer Building (MC) 5158


Brandt and Thomassé proved that every n-vertex triangle-free graph
with minimum degree greater than (1/3)n is 4-colourable. On the other
hand, Hijnal proved that, for each ε>0, there are triangle-free graphs
with minimum degree greater than (1/3 - ε)n$ that have arbitrarily large
chromatic number. The proof of Brandt and Thomassé’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.