Coloring Graphs From Random Lists

Given positive integers (Formula presented.) and a graph (Formula presented.), a family of lists (Formula presented.) is said to be a random (Formula presented.) -list-assignment if for every (Formula presented.) the list (Formula presented.) is a subset of (Formula presented.) of size (Formula presented.), chosen uniformly at random and independently of the choices of all other vertices. An (Formula presented.) -vertex graph (Formula presented.) is said to be a.a.s. (Formula presented.) -colorable if (Formula presented.), where (Formula presented.) is a random (Formula presented.) -list-assignment. We prove that if (Formula presented.) and (Formula presented.), where (Formula presented.) is the maximum degree of (Formula presented.) and (Formula presented.) is an integer, then (Formula presented.) is a.a.s. (Formula presented.) -colorable. This is not far from being the best possible, forms a continuation of the so-called palette sparsification results, and proves in a strong sense a conjecture of Casselgren. Furthermore, we consider this problem under the additional assumption that (Formula presented.) is (Formula presented.) -free for some graph (Formula presented.). For various graphs (Formula presented.), we estimate the smallest (Formula presented.) for which any (Formula presented.) -free (Formula presented.) -vertex graph (Formula presented.) is a.a.s. (Formula presented.) -colorable for every (Formula presented.). This extends and improves several results of Casselgren.