Colouring locally sparse graphs with the first moment method

Abstract

We give a short proof of a bound on the list chromatic number of graphs $G$ of maximum degree $\Delta$ where each neighbourhood has density at most $d$, namely ${\chi }_{\ell }(G)\le (1+o(1))\frac{\Delta }{\ln \frac{\Delta }{d+1}}$ as $\frac{\Delta }{d+1}\to \infty$. This bound is tight up to an asymptotic factor $2$, which is the best possible barring a breakthrough in Ramsey theory, and strengthens results due to Vu, and more recently Davies, P., Kang, and Sereni. Our proof relies on the first moment method, and adapts a clever counting argument developed by Rosenfeld in the context of non-repetitive colourings. As a final touch, we show that our method provides an asymptotically tight lower bound on the number of colourings of locally sparse graphs.

References in corpus (2)

• Coloring graphs with forbidden bipartite subgraphs
• Counting colorings of triangle-free graphs