Coloring triangle‐free graphs with local list sizes. Issue 3 (13th July 2020)

• Record Type: Journal Article
• Authors: Davies, Ewan; de Joannis de Verclos, Rémi; Kang, Ross J.; Pirot, François
• Is Part Of: Random structures & algorithms. Volume 57:Issue 3(2020)
• Page Start: 730
• Page End: 744
• Publication Date: 2020-07-13
• Subjects: hard‐core model -- list coloring -- triangle‐free graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20945
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We prove two distinct and natural refinements of a recent breakthrough result of Molloy (and a follow‐up work of Bernshteyn) on the (list) chromatic number of triangle‐free graphs. In both our results, we permit the amount of color made available to vertices of lower degree to be accordingly lower. One result concerns list coloring and correspondence coloring, while the other concerns fractional coloring. Our proof of the second illustrates the use of the hard‐core model to prove a Johansson‐type result, which may be of independent interest.