An analogue of Hajós' theorem for the circular chromatic number (Q2723478)

Given two integers, \(k,d\) with \(k\geq d,\) a \(( k,d) \)-coloring of a graph \(G\) is a coloring \(\phi \) of the vertices of \(G\) with colors \(0,1,\dots ,k-1,\) such that \(d\leq |\phi (x)-\phi (y)|\leq k-d,\) for any two adjacent vertices \(x\) and \(y\) of \(G.\) The circular chromatic number, \(\chi _{c}(G),\) (also known as the star chromatic number) is the infimum of the ratio \(\frac{k}{d}\) for which there exists a \(( k,d) \)-coloring. The graph \(G_{k}^{d}\) is defined as the graph with vertex set \(\{0,1,\ldots ,k-1\}\) and edge set \(\{ij:d\leq |i-j|\leq k-d\}.\) The author designs a set of graph operations and shows that, for \(\frac{k}{d}\geq 3,\) all graphs with \(\chi _{c}(G)\geq \frac{k}{d}\) can be constructed from copies of the graph \(G_{d}^{k}\) by repeatedly applying those operations.