Construction of sparse graphs with prescribed circular colorings

This paper constructively proves the following result: Suppose that k greater than or equal to 3d - 2, (k,d)= 1, A is a finite set and f(1), f(2),...,f(n) are mappings from A to {0, 1,...,k - 1}. Then, for any integer I, there is a graph G = (V,E) of girth at least l with A subset of V, such that G has exactly n (k,d)-colorings (up to a permutation of the colors) g(1), g(2),..., g(n), and each g, is an extension of f(i). This result generalizes a result of Muller who proved this for k-colorings. Note that for n = 1, the method presented in this paper gives a construction of uniquely (k,d)-colorable graphs. (C) 2001 Elsevier Science B.V. All rights reserved.