An analogue of Hajós' theorem for the circular chromatic number. II (Q1409583): Difference between revisions

For a graph \(G=\left( V,E\right) \) an \(r\)-colouring \(f\) of \(G\) is a mapping \(f:V\rightarrow [0,r)\) such that \(1\leq \left|f\left( x\right) -f\left( y\right) \right|\leq r-1\) for every edge \(xy\) of \(G\). The circular chromatic number \(\chi _{c}\left( G\right) \) is the infimum of those \(r\) for which \(G\) has an \(r\)-colouring. For \(k\geq 2d\) the circular complete graph \(K_{k/d}\) is the graph with vertex set \(\{0,1,\ldots, k-1\}\) in which \(i\) is adjacent to \(j\) if and only if \(d\leq \left|i-j\right|\leq k-d\). In a previous paper [Proc. Am. Math. Soc. 129, 2845-2852 (2001; Zbl 0971.05042)] the author designed a set of graph operations and showed 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 \(K_{k/d}\) by repeatedly applying these operations. In this paper he designs a set of graph operations to prove a similar result for the case \(2\leq \frac{k}{d}<3.\) The combination of these results is a complete analogue of Hajos' theorem (which states that every graph with chromatic number at least \(k\) can be constructed from copies of \(K_{k}\) by repeatedly applying three operations: adding vertices and edges, identifying nonadjacent vertices and applying Hajos' sum) for the circular chromatic number.