Colouring triangle-free graphs with local list sizes

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 colour made available to vertices of lower degree to be accordingly lower. One result concerns list colouring and correspondence colouring, while the other concerns fractional colouring. 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.

16 pages; v2 includes minor corrections after review; to appear in Random Structures & Algorithms

References in corpus (6)

• On the average size of independent sets in triangle-free graphs
• Independent Sets, Matchings, and Occupancy Fractions
• The Johansson--Molloy Theorem for DP-Coloring
• Colouring triangle-free graphs with local list sizes
• Separation choosability and dense bipartite induced subgraphs
• Bounding $\chi$ by a fraction of $\Delta$ for graphs without large cliques

Cited by in corpus (10)

• Colouring triangle-free graphs with local list sizes
• Separation choosability and dense bipartite induced subgraphs
• Independent transversals in bipartite correspondence-covers
• An algorithmic framework for colouring locally sparse graphs
• The $\chi$-Ramsey problem for triangle-free graphs
• Asymmetric list sizes in bipartite graphs
• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Colouring locally sparse graphs with the first moment method
• Uniformly Random Colourings of Sparse Graphs
• Local girth choosability of planar graphs