Circular Chromatic Number and Mycielski Graphs

As a natural generalization of graph coloring, Vince introduced the star chromatic number of a graph G and denoted it by ^*(G). Later, Zhu called it circular chromatic number and denoted it by _c(G). Let (G) be the chromatic number of G. In this paper, it is shown that if the complement of G is non-hamiltonian, then _c(G)=(G). Denote by M(G) the Mycielski graph of G. Recursively define M^m(G)=M(M^m–1(G)). It was conjectured that if mn–2, then _c(M^m(K_n))=(M^m(K_n)). Suppose that G is a graph on n vertices. We prove that if , then _c(M(G))=(M(G)). Let S be the set of vertices of degree n–1 in G. It is proved that if |S| 3, then _c(M(G))=(M(G)), and if |S| 5, then _c(M²(G))=(M²(G)), which implies the known results of Chang, Huang, and Zhu that if n3, _c(M(K_n))=(M(K_n)), and if n5, then _c(M²(K_n))=(M²(K_n)).* Research supported by Grants from National Science Foundation of China and Chinese Academy of Sciences.