Graphs of Large Girth with Prescribed Partial Circular Colourings

This paper completes the constructive proof of the following result: Suppose p/q2 is a rational number, A is a finite set and f₁,f₂,···,f_n are mappings from A to {0,1,···,p–1}. Then for any integer g, there is a graph G=(V,E) of girth at least g with such that G has exactly n (p,q)-colourings (up to equivalence) g₁,g₂,···,g_n, and each g_i is an extension of f_i. A probabilistic proof of this result was given in [8]. A constructive proof of the case p/q3 was given in [7].This research was partially supported by the National Science Council under grant NSC91-2115-M-110-004