| Abstract: | 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  of size  . Such a list assignment is called a random  ‐list assignment. In this paper, we are interested in determining the asymptotic probability (as n →∞) of the existence of a proper coloring φ of G, such that  for every vertex v of G, a so‐called L‐coloring. We give various lower bounds on σ, 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  and  , then the probability that G has an L‐coloring tends to 1 as  . If  and  , then the same conclusion holds provided that  . We also give related results for other bounds on Δ, when k is constant or a strictly increasing function of n. |
