Circular chromatic number for iterated Mycielski graphs (Q1877680)

Given positive integers \(k,d,\;k \geq 2d\), a \((k,d)\)-coloring of a graph \(G\) is a mapping \(c:\;V(G) \to \{0,1,\dots, k-1\}\) such that for each edge \(xy \in E(G)\), \(| c(x) - c(y)| _k \geq d\) (where \(| a-b| _k = \min\{ | a-b| ,k-| a-b| \}\)). The star chromatic number \(\chi^*(G)\) is defined as the infimum of \(\frac{k}{d}\) over the pairs \((k,d)\) such that \(G\) has a \((k,d)\)-coloring (see \textit{A. Vince} [J. Graph Theory 12, 551--559 (1988; Zbl 0658.05028)]; this invariant is also known as the circular chromatic number \(\chi_c(G)\) introduced by \textit{X. Zhu} [J. Graph Theory 16, 557--569 (1992; Zbl 0766.05033)]). This paper deals with the circular chromatic number for iterated Mycielski graphs (for an \(n\)-vertex graph \(G\) with \(V(G) = \{x_1,\dots,x_n\}\), the Mycielski graph \(M(G)\) of \(G\) is obtained from \(G\) by adding \(n+1\) new vertices \(x_1',x_2',\dots,x_n',u\) such that each \(x_i',i=1,\dots,n\) is joined to the neighbours of \(x_i\) and to \(u\); the iterated Mycielski graph is defined recursively by \(M^m(G) = M(M^{m-1}(G))\). It is proved that if \(G\) has a vertex \(x\) adjacent to every other vertex, then \(\chi_c(M(G)) = \chi(M(G))\) if \(\chi_c(G-x) > \chi(G) - \frac{1}{2}\) and \(G\) is not a star, otherwise \(\chi_c(M(G)) = \chi(M(G)) - \frac{1}{2}\). Furthermore, it is proved that \(\chi_c(M^t(K_m)) = \chi(M^t(K_m))\) if \(m \geq 2^{t-1} + 2t - 2\) and \(t \geq 2\); this improves a result of \textit{H. Hajiabolhassan} and \textit{X. Zhu} [J. Graph Theory 44, 106--115 (2003; Zbl 1030.05047)].