A GENERALIZATION OF LINE GRAPHS - (X,Y)-INTERSECTION GRAPHS

Given a pair (X, Y) of fixed graphs X and Y, the (X, Y)-intersection g raph of a graph G is a graph whose vertices correspond to distinct ind uced subgraphs of G that are isomorphic to Y, and where two vertices a re adjacent iff the intersection of their corresponding subgraphs cont ains an induced subgraph isomorphic to X. This generalizes the notion of line graphs, since the line graph of G is precisely the (K-1, K-2)- intersection graph of G. In this paper, we consider the forbidden indu ced subgraph characterization of (X, Y)-intersection graphs for variou s (X, Y) pairs; such consideration is motivated by the characterizatio n of line graphs through forbidden induced subgraphs. For this purpose , we restrict our attention to hereditary pairs (a pair (X, Y) is here ditary if every induced subgraph of any (X, Y)-intersection graph is a lso an (X, Y)-intersection graph), since only for such pairs do (X, Y) -intersection graphs have forbidden induced subgraph characterizations . We show that for hereditary 2-pairs (a pair (X, Y) is a 2-pair if Y contains exactly two induced subgraphs isomorphic to X), the family of line graphs of multigraphs and the family of line graphs of bipartite graphs are the maximum and minimum elements, respectively, of the pos et on all families of (X, Y)-intersection graphs ordered by set inclus ion. We characterize 2-pairs for which the family of (X, Y)-intersecti on graphs are exactly the family of line graphs or the family of line graphs of multigraphs. (C) 1996 John Wiley & Sons, Inc.