Construction of sparse graphs with prescribed circular colorings Original Research Article

This paper constructively proves the following result: Suppose that k⩾3d−2, (k,d)=1, A is a finite set and f1,f2,…,fn are mappings from A to {0,1,…,k−1}. Then, for any integer l, there is a graph G=(V,E) of girth at least l with A⊂V, such that G has exactly n (k,d)-colorings (up to a permutation of the colors) g1,g2,…,gn, and each gi is an extension of fi. This result generalizes a result of Müller 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.