TY - JOUR
T1 - Circular chromatic number and a generalization of the construction of Mycielski
AU - Lam, Peter Che Bor
AU - Lin, Wensong
AU - Gu, Guohua
AU - Song, Zengmin
N1 - Funding Information:
This work is partially supported by FRG, Hong Kong Baptist University, Hong Kong; and NSFC, China, under Grant 10171013.
PY - 2003/11
Y1 - 2003/11
N2 - 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, χ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.
AB - 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, χ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.
KW - Circular chromatic number
KW - Generalized Mycielski's graph
UR - http://www.scopus.com/inward/record.url?scp=0344118774&partnerID=8YFLogxK
U2 - 10.1016/S0095-8956(03)00070-4
DO - 10.1016/S0095-8956(03)00070-4
M3 - Journal article
AN - SCOPUS:0344118774
SN - 0095-8956
VL - 89
SP - 195
EP - 205
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -