Colouring powers of cycles from random lists

AbstractLet Cnk be the kth power of a cycle on n vertices (i.e. the vertices of Cnk are those of the n-cycle, and two vertices are connected by an edge if their distance along the cycle is at most k). For each vertex draw uniformly at random a list of size c from a base set S of size s=s(n). In this paper we solve the problem of determining the asymptotic probability of the existence of a proper colouring from the random lists for all fixed values of c,k, and growing n