Intersection multigraphs of uniform hypergraphs
A hypergraph \(H=(V,\{X_i \mid i\in I\})\) is \(k\)-uniform if all hyperedges \(X_i\) have the same cardinality \(k\); it is \(k\)-conformal if there is some graph \(G\) such that \(H\) is isomorphic to the hypergraph of all cliques with \(k\) vertices of \(G\). The intersection multigraph of \(H\) has \(\{x_i \mid i\in I\}\) as vertex set, and two distinct vertices \(x_i\), \(x_j\) are joined by \(| X_i\cap X_j| \) parallel edges. While the recognition problem of intersection multigraphs of \(k\)--uniform hypergraphs \((k\geq 3)\) is NP-complete, the author shows that intersection multigraphs of 3-uniform, 3-conformal hypergraphs can be recognized and the (essentially unique) root hypergraph can be reconstructed in polynomial time. Intersection multigraphs of \(k\)-uniform, \(k\)-conformal hypergraphs \((k\geq 4)\) with one additional property are also discussed.
scientific article; zbMATH DE number 1234340