BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

On a local version of Reed's conjecture Postle, Luke


In 1998, Reed conjectured that the chromatic number of a graph is at most the average of its maximum degree plus one and its clique number (rounded up). As evidence for his conjecture, he proved that it is at most some non-trivial convex combination of the two. Recently, Michelle Delcourt and I proved the same is true for list chromatic number. Tom Kelly and I meanwhile conjectured that a `local' version of Reed's conjecture wherein the parameters are replaced by local parameters (list size, degree and clique number of neighborhood) and proved a non-trivial convex combination under some mild assumptions. 

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International