![]() |
![]() |
University of Birmingham > Talks@bham > Combinatorics and Probability seminar > On the List Coloring Version of Reed's Conjecture
![]() On the List Coloring Version of Reed's ConjectureAdd to your list(s) Download to your calendar using vCal
If you have a question about this talk, please contact Guillem Perarnau. 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 Postle proved for large enough maximum degree, a fraction of 1/26 away from the upper bound holds, a signficant step towards the conjectured value of 1/2. Using new techniques, we show that the list-coloring version holds; for large enough maximum degree, a fraction of 1/13 suffices for list chromatic number. This result implies that 1/13 suffices for ordinary chromatic number as well. This is joint work with Luke Postle. This talk is part of the Combinatorics and Probability seminar series. This talk is included in these lists:Note that ex-directory lists are not shown. |
Other listsLab Lunch School of Metallurgy and Materials Colloquia Electromagnetic Communications and Sensing Research Seminar SeriesOther talksSylow branching coefficients for symmetric groups TBC Geometry of alternating projections in metric spaces with bounded curvature Provably Convergent Plug-and-Play Quasi-Newton Methods for Imaging Inverse Problems Quantum simulations using ultra cold ytterbium Extending the Lax type operator for finite W-algebras |