Circular chromatic numbers of Mycielski's graphs
Resource
Discrete mathematics 205,23-37
Journal
Discrete mathematics 205
Pages
23-37
Date Issued
1999
Date
1999
Author(s)
Chang, Gerard J.
Huang, Ling-Ling
Zhu, Xu-Ding
DOI
2006092712111596033
Abstract
In 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.
Subjects
Circular chromatic number
Mycielski's graphs
Girth
Homomorphism
Connectivity
Critical graph
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
073.pdf
Size
185.55 KB
Format
Adobe PDF
Checksum
(MD5):95831c092dd838a93771e8c7b3c33752