Department of Mathematics,
University of California San Diego
****************************
Math 269 - Combinatorics
Prof. Michael Molloy
University of Toronto
An improved bound for the List Colouring Conjecture
Abstract:
The List Colouring Conjecture posits that the list edge chromatic number of any graph is equal to the edge chromatic number, and thus is at most D+1 where D is the maximum degree. This means that if each edge is assigned a list of $D+1$ colours then it is always possible to obtain a proper edge colouring by choosing one colour from each list.
In the 1990's, Khan proved that one can always obtain a proper edge colouring from lists of size $D+o(D)$, then Molloy and Reed obtained $D+D^{1/2}\mathrm{poly}(\log D)$. We improve that bound to $D+D^{2/5}\mathrm{poly}(\log D)$
Host: Lutz Warnke
May 21, 2024
2:00 PM
APM 7321
Research Areas
Combinatorics****************************
