Date
Tue, 25 Apr 2017
14:30
Location
L3
Speaker
Marthe Bonamy
Organisation
Bordeaux

The chromatic number of a graph is trivially bounded from above by the maximum degree plus one, and from below by the size of a largest clique. Reed proved in 1998 that compared to the trivial upper bound, we can always save a number of colors proportional to the gap between the maximum degree and the size of a largest clique. A key step in the proof deals with how to spare colors in a graph whose every vertex "sees few edges" in its neighborhood. We improve the existing approach, and discuss its applications to Reed's theorem and strong edge coloring.  This is joint work with Thomas Perrett (Technical University of Denmark) and Luke Postle (University of Waterloo).

Please contact us with feedback and comments about this page. Last updated on 04 Apr 2022 15:24.