國立臺灣大學數學系Chang, Gerard J.Gerard J.ChangHuang, Ling-LingLing-LingHuangZhu, Xu-DingXu-DingZhu2006-09-272018-06-282006-09-272018-06-281999http://ntur.lib.ntu.edu.tw//handle/246246/2006092712111596033In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski devel- oped a graph transformation that transforms a graph G into a new graph (G), we now call the Mycielskian of G, which has the same clique number as G ; whose chromatic number equals (G)+1. Let n(G)=(n−1(G)) for n>2. This paper investigates the circular chromatic num- bers of Mycielski's graphs. In particular, the following results are proved in this paper: (1) for any graph G of chromatic number n; c(n−1(G))6(n−1(G)) − 1 2 ; (2) if a graph G satises c(G)6(G) − 1 d with d = 2 or 3, then c(2(G))6(2(G)) − 1 d ; (3) for any graph G of chromatic number 3, c((G)) = ((G)) = 4; (4) c((Kn)) = ((Kn)) = n + 1 for n>3 and c(2(Kn)) = (2(Kn)) = n + 2 for n>4.application/pdf190004 bytesapplication/pdfzh-TWCircular chromatic numberMycielski's graphsGirthHomomorphismConnectivityCritical graphjournal articlehttp://ntur.lib.ntu.edu.tw/bitstream/246246/2006092712111596033/1/073.pdf