A class of graphs is hereditary if it is closed under taking induced subgraphs. Classes associated with graph representations have "composition sequences" and we show that this concept is equivalent to a notion of "amalgamation" which generalizes disjoint union of graphs. We also discuss how general hereditary classes of graphs are built up from representation classes.
1. BACKGROUND
In this paper all graphs are undirected, loopless, and without multiple edges. Unless stated otherwise, all graphs are finite.
We will write G I H when G is an induced subgraph of H . In general we will not distinguish between isomorphic graphs and will also write G 5 H when G is isomorphic to an induced subgraph of H.
A class of graphs G is called hereditury if it is closed under induced subgraphs, i.e., if H β¬ G and G 5 H then G β¬ G. Certain hereditary classes of graphs arise in connection with representations of graphs. Let C be a family of sets. A graph G has a 2-intersection representation if there exists an injec-
The class of all graphs with 2-intersection representations is called an intersection class. It is immediate that intersection classes are hereditary. However, they have one additional property (see [ 5 ] ) :
Let G be a class of graphs. A composition sequence for G is a sequence of graphs G ' , G2, . . . such that
(1) G' E G for all i, ( 2 ) G' I G'" for all i, and
(3) for all G E G there exists a j such that G 5 G'.