Construction of sparse graphs with prescribed circular colorings (Q5936037)

Suppose that \(G=(V,E)\) is a graph and \(k,d\) are positive integers with \(k\geq 2d\) and \((k,d)=1\). A \((k,d)\)-coloring of \(G\) is a mapping \(f:V\rightarrow \{0,1,\ldots, k-1\}\) such that for every edge \(xy\in E\), min\(\{|f(x)-f(y)|, k-|f(x)-f(y)|\}\geq d\). In this paper the following property is constructively proved: If \(k\geq 3d-2, (k,d)=1\), \(A\) is a finite set and \(f_{1},\ldots ,f_{n}\) are mappings from \(A\) to \(\{0,1,\ldots ,k-1\}\), then for any integer \(l\), there is a graph \(G=(V,E)\) of girth at least \(l\) with \(A\subset V\), such that \(G\) has exactly \(n\) \((k,d)\)-colorings \(g_1,\dots, g_n\) (up to a permutation of the colors), and each \(g_{i}\) is an extension of \(f_{i}\). This result generalizes a result of \textit{V. Müller} who proved this for \(k\)-colorings [Discrete Math. 26, No. 2, 165-176 (1979; Zbl 0407.05037)]. Note that for \(n=1\), the method presented in this paper gives a construction of uniquely \((k,d)\)-colorable graphs. Some other results about the projectivity of the graphs \(G_{d}^{k}\) defined in the paper are also presented.