Coloring complete bipartite graphs from random lists

Let K_n,n be the complete bipartite graph with n vertices in each side. For each vertex draw uniformly at random a list of size k from a base set S of size s = s(n). In this paper we estimate the asymptotic probability of the existence of a proper coloring from the random lists for all fixed values of k and growing n. We show that this property exhibits a sharp threshold for k ≥ 2 and the location of the threshold is precisely s(n) = 2n for k = 2 and approximately for k ≥ 3. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006