Colouring graphs from random lists

Given positive integers k ≤ m and a graph G, a family of lists L = (v) : v ∈ V(G)\ is said to be a random $(k,m)$-list-assignment if for every v ∈ V(G) the list $L(v)$ is a subset of \1, …, 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 limn → ∞ P(G is L-colourable) = 1, where L is a random $(k,m)$-list-assignment. We prove that if m n1/k² Δ1/k and m ≥ 3 k² Δ, where Δ is the maximum degree of G and k ≥ 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.