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)) D e l t a / l o g D e l t a

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

D e l t a

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)) D e l t a / l o g D e l t a

, as implies a more general result due to Amini and Reed. We also prove that lists of length

2 (r - 2) D e l t a l o g_{2} l o g_{2} D e l t a / l o g_{2} D e l t a

are sufficient if one replaces the triangle by any

K_{r}

with

r g e q 4

, pushing also slightly the multiplicative factor of

200 r

from Bernshteyn's result down to

2 (r - 2)

. All bounds presented are also valid within the more general setting of correspondence colourings.

Recommendations

Cites work

This page was built for publication: On triangle-free list assignments