Circular chromatic number and a generalization of the construction of Mycielski

Peter Che Bor Lam*, Wensong Lin, Guohua Gu, Zengmin Song

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

23 Citations (Scopus)

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(Kn) for any m(≥0) and n(≥2). We prove that for any odd integer n≥3 and any nonnegative integer m, χcm (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 χcm (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.

Original languageEnglish
Pages (from-to)195-205
Number of pages11
JournalJournal of Combinatorial Theory. Series B
Volume89
Issue number2
DOIs
Publication statusPublished - Nov 2003
Externally publishedYes

Scopus Subject Areas

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

User-Defined Keywords

  • Circular chromatic number
  • Generalized Mycielski's graph

Fingerprint

Dive into the research topics of 'Circular chromatic number and a generalization of the construction of Mycielski'. Together they form a unique fingerprint.

Cite this