Extension of hereditary classes with substitutions

Let G and H be graphs. A substitution of H in G instead of a vertex nu is an element of V(G) is the graph G(nu --> H), which consists of disjoint union of H and G - nu with the additional edge-set {xy: x is an element of V(H), y is an element of N-G(nu)}. For a hereditary class of graphs P, the substitutional closure of P is defined as the class P* consisting of all graphs which can be obtained from graphs in P by repeated substitutions. Let P be an arbitrary hereditary class for which a characterization in terms of forbidden induced subgraphs is known. We propose a method of constructing forbidden induced subgraphs for P*. (C) 2003 Elsevier Science B.V. All rights reserved.