![]() |
![]() |
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 listscomputer sience Metamaterials and Nanophotonics Group Seminars Molecular and Medical Physics Seminar SeriesOther talksTBA Hunt for an Earth-twin TBC TBA The tragic destiny of Mileva Marić Einstein Life : it’s out there, but what and why ? |