On Reed's conjecture

Series
Graph Theory Seminar
Time
Wednesday, March 16, 2016 - 3:05pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Luke Postle – Department of C&O, University of Waterloo
Organizer
Robin Thomas
In 1998, Reed proved that the chromatic number of a graph is bounded away from its trivial upper bound, its maximum degree plus one, and towards its trivial lower bound, its clique number. Reed also conjectured that the chromatic number is at most halfway in between these two bounds. We prove that for large maximum degree, that the chromatic number is at least 1/25th in between. Joint work with Marthe Bonamy and Tom Perrett.