On Reed's conjecture

Graph Theory Seminar
Wednesday, March 16, 2016 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Department of C&O, University of Waterloo
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.