Circular chromatic number and Mycielski graphs (Q5894920): Difference between revisions

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)\), \(d \leq | c(x) - c(y)| \leq k-d\). The star chromatic number is defined as \(\chi^*(G) = \inf\{\frac{k}{d}: G\text{ has a }(k,d)\)-coloring\}, see \textit{A. Vince} [J. Graph Theory 12, No. 4, 551--559 (1988; Zbl 0658.05028)]; this invariant is the same as the circular chromatic number \(\chi_c(G)\) introduced by \textit{X. Zhu} [J. Graph Theory 16, No. 6, 557--569 (1992; Zbl 0766.05033)]. In the first part of the paper under review, it is shown that if the complement of \(G\) is non-Hamiltonian, then \(\chi_c(G) = \chi(G)\); further, for an \(n\)-vertex graph \(G\), if there is a set \(S=\{a,b,c\} \subseteq V(G)\) such that \(N(S) \cup S \neq V(G)\) and \(\deg(a) + \deg(b) + \deg(c) \geq 3(n-3)\), then \(\chi_c(G) = \chi(G)\). The second part deals with Mycielski graphs (the Mycielski graph \(M(G)\) of a graph \(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))\)). The author proves that, for an \(n\)-vertex graph \(G\), if \(\chi(G) \geq \frac{n+3}{2}\), then \(\chi_c(M(G)) = \chi(M(G))\). Moreover, it is proved that if there are at least three vertices of degree \(n-1\) in \(G\), then \(\chi_c(M(G)) = \chi(M(G))\), and if there are at least five such vertices, then \(\chi_c(M^2(G)) = \chi(M^2(G))\). This implies the known results of \textit{G. J. Chang, L. Huang} and \textit{X. Zhu} [Discrete Math. 205, No. 1--3, 23--37 (1999; Zbl 0941.05026)].