比利时vs摩洛哥足彩
,
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****************************
