Multi-intersection graphs (Q1978159)

Multi-intersection graphs are defined as a generalization of intersection graphs. Vertices of a multi-intersection graph correspond to sets in a multi-family of sets (some sets in a multi-family may be repeated). Two vertices are adjacent if the corresponding sets have nonempty intersection. A class of graphs \(P\) is called hereditary if it is closed according to induced subgraphs. Suppose that \(P\) be a hereditary class of intersection graphs. \(P^{m}\) denote the class of multi-intersection graphs with the same family of subsets and multiplicity of each set at most \(m\). It is possible to characterize a hereditary class \(P\) in terms of forbidden induced subgraphs. There exists a class \(Z\) of graphs such that \(G\) is in \(P\) if and only if no induced subgraph of \(G\) is isomorphic to any graph in \(Z\). The author solves the problem of constructing the class of forbidden graphs \(Z\left( m\right)\) for the class \(P^{m}\). The class \(P\) and the corresponding class of forbidden graphs \(Z\) are given. This method is applied to the line graph of a multigraph and the class of the forbidden subgraphs is obtained.