Colouring complete bipartite graphs from random lists

الأصل · EN

Let Kₙ,ₙ 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 colouring 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 s(n)=n2ᵏ⁻¹ 2 for k≥ 3.