Recognizing intersection graphs of linear uniform hypergraphs (Q1376077): Difference between revisions

Let \(H =(V,E)\) be a hypergraph with vertex set \(V\) and edge set \(E\). If two distinct hyperedges of \(H\) share one common vertex, they define an edge of the intersection graph of \(H\), where \(E\) is taken as its vertex set. A hypergraph is linear if any two distinct hyperedges have at most one common vertex. The authors show the existence of a polynomial algorithm for deciding whether a graph of minimum degree \( \delta \geq 19\) is the intersection graph of a linear 3-uniform hypergraph. This improves some result in \textit{R. N. Naik, S. B. Rao, S. S. Shrikhande}, and \textit{N. M. Singhi} [Eur. J. Comb. 3, 159-172 (1982; Zbl 0491.05046)].