A NEIGHBORHOOD CONDITION WHICH IMPLIES THE EXISTENCE OF A CLASS OF D-CHROMATIC SUBGRAPHS

A graph G of order n satisfies the neighborhood condition NCk > s if a ny collection of k independent vertices is collectively adjacent to mo re than s vertices. Given a family H of graphs, the decomposition clas s beta(H) is the family of graphs B with the property that for some H epsilon H of chromatic number d, H contains B as an induced subgraph a nd [V(H) - V(B)] is (d - 2) colorable. Let H be a family of d-chromati c graphs, B an element of beta(H) such that B contains an s-matching a s an induced subgraph. Thus the cardinality of one of the partite sets of B is s + r for some integer r greater than or equal to 0. We show that if t is a fixed positive integer, G is a graph of sufficiently la rge order n that satisfies the neighborhood condition NCk > (d - 2)/(d - 1)n + cn(1-1/r),a subgraph. (C) 1994 John Wiley & Sons, Inc.