Hall ratio of the Mycielski graphs

Let n (G) denote the number of vertices of a graph G and let a (G) be the independence number of G, the maximum number of pairwise nonadjacent vertices of G. The Hall ratio of a graph G is defined by [GRAPHICS] where the maximum is taken over all induced subgraphs H of G. It is obvious that every graph G satisfies omega(G) <= rho(G) <= chi(G) where omega and chi denote the clique number and the chromatic number of G, respectively. We show that the interval [omega(G), rho(G)] can be arbitrary large by estimating the Hall ratio of the Mycielski graphs. (c) 2006 Elsevier B.V. All rights reserved.