## Abstract

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_{3}), 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.

Original language | English |
---|---|

Pages (from-to) | 195-205 |

Number of pages | 11 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 89 |

Issue number | 2 |

DOIs | |

Publication status | Published - Nov 2003 |

Externally published | Yes |

## Scopus Subject Areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## User-Defined Keywords

- Circular chromatic number
- Generalized Mycielski's graph