报告题目：Coloring graphs from triangle-free lists

报告人：Jakub Przybyło，AGH University of Krakow

报告时间：2024年11月8日（周五）14:30-17:30

报告地点：20-308

摘要：We shall discuss an observation that Bernshteyn’s version of the proof of the breakthrough result due to 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. In the same vein, it can also proven that lists of length 2(r −2)∆ log2 log2 ∆/ log2 ∆ are sufficient if one replaces the triangle by any Kr with r ≥ 4, which pushes slightly the multiplicative factor of 200r from Bernshteyn’s result down to 2(r − 2). All bounds mentioned are also valid within the more general setting of correspondence colourings.

邀请人：朱绪鼎