A NEIGHBORHOOD CONDITION WHICH IMPLIES THE EXISTENCE OF A COMPLETE MULTIPARTITE SUBGRAPH

Given a graph G and u is-an-element-of V(G), the neighborhood N(u)={u is-an-element-of V(G)\uv is-an-element-of E(G)}. We define NC(k)(G)= m in \or N(u(i))\ where the minimum is taken over all k independent sets {u1,...,u(k)} of vertices in V(G). We shall show that if G is a graph of order n that satisfies the neighborhood condition NC(k)(G) > d-2/d -1 n+cn1-1/r for some real number c = c(m, d, k, r) then for sufficien tly large n, G contains at least one copy of a K (r, m, ..., m(d-1)) w here m(i)=m for each i and r greater-than-or-equal-to m. When r = 1, 2 or 3, this result is best possible.