On triangle-free list assignments

Abstract

We show that Bernshteyn's proof of the breakthrough result of Molloy that triangle-free graphs are choosable from lists of size $(1+o(1))\Delta /\log \Delta$ can be adapted to yield a stronger result. In particular one may prove that such list sizes are sufficient to colour any graph of maximum degree $\Delta$ provided that vertices sharing a common colour in their lists do not induce a triangle in $G$, which encompasses all cases covered by Molloy's theorem. This was thus far known to be true for lists of size $(1000+o(1))\Delta /\log \Delta$, as implies a more general result due to Amini and Reed. We also prove that lists of length $2(r-2)\Delta {\log }_2{\log }_2\Delta /{\log }_2\Delta$ are sufficient if one replaces the triangle by any $K_r$ with $r\ge 4$, pushing also slightly the multiplicative factor of $200r$ from Bernshteyn's result down to $2(r-2)$. All bounds presented are also valid within the more general setting of correspondence colourings.

16 pages