Circular chromatic number and a generalization of the construction of Mycielski

AbstractIn this paper, we introduce a graph transformation analogous to that of Mycielski. Given a graph G and any integer m, one can transform G into a new graph μm(G), the generalized Mycielskian of G. Many basic properties of μm(G) were established in (Lam et al., Some properties of generalized Mycielski's graphs, to appear). Here we completely determine the circular chromatic number of μm(Kn) for any m(⩾0) and n(⩾2). We prove that for any odd integer n⩾3 and any nonnegative integer m, χc(μm(Kn))=χ(μm(Kn))=n+1. This answers part of the question raised by Zhou (J. Combin. Theory Ser. B 70 (1997) 245) or that by Zhu (Discrete Math. 229 (2001) 371). Because μm(K3), for arbitrary m, is a planar graph with connectivity 3 and maximum degree 4, it provides another counterexample to a question asked by Vince (J. Graph Theory 17 (1993) 349). For any positive even number n(⩾2) and any nonnegative integer m, we show that χc(μm(Kn))=n+(1/t), where t=⌊2m/n⌋+1. This gives a family of arbitrarily large critical graphs G with high connectivity and small maximum degree for which χc(G) can be arbitrarily close to χ(G)−1