14:30
Reed conjectured in 1998 that the chromatic number of a graph should be at most the average of the clique number (a trivial lower bound) and maximum degree plus one (a trivial upper bound); in support of this conjecture, Reed proved that the chromatic number is at most some nontrivial convex combination of these two quantities. King and Reed later showed that a fraction of roughly 1/130000 away from the upper bound holds. Motivated by a paper by Bruhn and Joos, last year Bonamy, Perrett, and I proved that for large enough maximum degree, a fraction of 1/26 away from the upper bound holds. Then using new techniques, Delcourt and I showed that the list-coloring version holds; moreover, we improved the fraction for ordinary coloring to 1/13. Most recently, Kelly and I proved that a 'local' list version holds with a fraction of 1/52 wherein the degrees, list sizes, and clique sizes of vertices are allowed to vary.