Characterizing intersection classes of graphs (Q1078582)

Let \(\Sigma\) denote a collection of sets, and let G be a graph with no loops or multiple edges. The author defines ''G has an intersection representation by sets in \(\Sigma\) '', to mean that there is some function f: V(G)\(\to \Sigma\) such that for \(v\neq w\in V\) we have f(v)\(\cap f(w)\neq \emptyset\) iff v adj w. The class of all graphs with intersection representations by sets in \(\Sigma\) is denoted by \(\Omega\) (\(\Sigma)\). An intersection class is any class of graphs which is \(\Omega\) (\(\Sigma)\) for some \(\Sigma\). Interval graphs are a well-known intersection class. The author gives a list of three conditions whose conjunction is necessary and sufficient for a given family of graphs to be an intersection class. The result is generalized to simplicial complexes and ''injective'' intersection classes in which the function f is required to be injective.