- 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.