Structure in Dense Triangle-free Graphs - Part 2
|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.
200 University Avenue West
Waterloo, ON N2L 3G1