Intersection Graphs and the Clique Operator

 Let P be a class of finite families of finite sets that satisfy a property P. We call ΩP the class of intersection graphs of families in P and CliqueP the class of graphs whose family of cliques is in P. We prove that a graph G is in ΩP if and only if there is a family of complete sets of G which covers all edges of G and whose dual family is in P. This result generalizes that of Gavril for circular-arc graphs and conduces those of Fulkerson-Gross, Gavril and Monma-Wei for interval graphs, chordal graphs, UV, DV and RDV graphs. Moreover, it leads to the characterization of Helly-graphs and dually chordal graphs as classes of intersection graphs. We prove that if P is closed under reductions, then CliqueP=Ω(P ^*∩H) (P ^*= Class of dual families of families in P). We find sufficient conditions for the Clique Operator, K, to map ΩP into ΩP ^*. These results generalize several known results for particular classes of intersection graphs. Furthermore, they lead to the Roberts-Spencer characterization for the image of K and the Bandelt-Prisner result on K-fixed classes. Received: August 18, 1997 Final version received: March 30, 1999