Circular chromatic numbers of Mycielski's graphs

Abstract

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph mu(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals chi(G) + 1. Let mu(n)(G) = mu(mu(n-1)(G)) for n greater than or equal to 2. This paper investigates the circular chromatic numbers of Mycielski's graphs. In particular, the following results are proved in this paper: (1) for any graph G of chromatic number n, chi(c)(mu(n-1)(G)) less than or equal to chi(mu(n-1)(G)) - 1/2; (2) if a graph G satisfies chi(c)(G) less than or equal to chi(G) - 1/d with d = 2 or 3, then chi(c)(mu(2)(G)) less than or equal to chi(mu(2)(G)) - 1/d; (3) for any graph G of chromatic number 3, chi(c)(mu(G)) = chi(mu(G)) = 4; (4) chi(c)(mu(K-n)) = chi(mu(K-n)) = n + 1 for n greater than or equal to 3 and chi(c)(mu(2)(K-n)) = chi(mu(2)(K-n)) = n + 2 for n greater than or equal to 4. (C) 1999 Elsevier Science B.V. All rights reserved.