Circular chromatic number and a generalization of the construction of Mycielski

In 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(K_n) for any m(≥0) and n(≥2). We prove that for any odd integer n≥3 and any nonnegative integer m, χ_c(μ_m (K_n)) = χ(μ_m (K_n)) = 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(K₃), 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 (K_n)) = 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.