Induced subgraphs of prescribed size

A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of Erdős and McKay we show that every graph G on n vertices for which q(G)≤ C log n contains an induced subgraph with exactly y edges, for every y between 0 and n^{δ (C)}. Our methods enable us also to show that under much weaker assumption, i.e., q(G) ≤ n/14, G still must contain an induced subgraph with exactly y edges, for every y between 0 and . © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 239–251, 2003