On triangle-free list assignments

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))Δ/\logΔ$ 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 $Δ$ 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))Δ/\logΔ$, as implies a more general result due to Amini and Reed. We also prove that lists of length $2(r-2)Δ\log_2\log_2Δ/\log_2Δ$ are sufficient if one replaces the triangle by any $K_r$ with $r\geq 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.

No reviews yet.

No comments yet.