SUBGRAPHS WITH A LARGE COCHROMATIC NUMBER

The cochromatic number of a graph G = (V, E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the chromatic num ber of G is n, then G contains a subgraph with cochromatic number al l east Omega(n/ln n). This is tight, up to the constant factor, and sett les a problem of Erdos and Gimbel. (C) 1997 John Wiley & Sons, Inc.