Colouring graphs from random lists

Abstract

Given positive integers $k\le m$ and a graph $G$, a family of lists $L=\{L(v):v\in V(G)\}$ is said to be a random $(k,m)$-list-assignment if for every $v\in V(G)$ the list $L(v)$ is a subset of $\{1,\dots ,m\}$ of size $k$, chosen uniformly at random and independently of the choices of all other vertices. An $n$-vertex graph $G$ is said to be a.a.s. $(k,m)$-colourable if ${\lim }_{n\to \infty }\mathbb{P}(G\text{ is }L-colourable)=1$, where $L$ is a random $(k,m)$-list-assignment. We prove that if $m\gg n^{1/k^2}{\Delta }^{1/k}$ and $m\ge 3k^2\Delta$, where $\Delta$ is the maximum degree of $G$ and $k\ge 3$ is an integer, then $G$ is a.a.s. $(k,m)$-colourable. This is not far from being best possible, forms a continuation of the so-called palette sparsification results, and proves in a strong sense a conjecture of Casselgren. Additionally, we consider this problem under the additional assumption that $G$ is $H$-free for some graph $H$. For various graphs $H$, we estimate the smallest $m$ for which an $H$-free $n$-vertex graph $G$ is a.a.s. $(k,m)$-colourable. This extends and improves several results of Casselgren.