Coloring graphs of various maximum degree from random lists

Let G=G(n) be a graph on n vertices with maximum degree = (n). Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k-subsets of a color set C of size C sigma=sigma(n). Such a list assignment is called a random(k,C)-list assignment. In this paper, we are interested in determining the asymptotic probability (as n ) of the existence of a proper coloring phi of G, such that phi(v)L(v) for every vertex v of G, a so-called L-coloring. We give various lower bounds on sigma, in terms of n, k, and , which ensures that with probability tending to 1 as n there is an L-coloring of G. In particular, we show, for all fixed k and growing n, that if sigma(n)=(n1/k21/k) and =O(n), then the probability that G has an L-coloring tends to 1 as n. If k2 and =(n1/2), then the same conclusion holds provided that sigma=(). We also give related results for other bounds on , when k is constant or a strictly increasing function of n.Funding Agencies|SVeFUM; Mittag-Leffler Institute