Recognizing Intersection Graphs of Linear Uniform Hypergraphs

A hypergraph is linear if any two distinct hyperedges have at most one common vertex. The existence of a polynomial algorithm is shown for deciding whether a graph of minimum degree δ ≥ 19 is the intersection graph of a linear 3-uniform hypergraph. This result improves a corollary of the finite forbidden subgraph characterization proved for δ ≥ 69 by Naik et al. in 8]. Essentially the same methods yield a polynomial recognition algorithm for the intersection graph of a linear r-uniform hypergraph, r ≥ 3, provided the minimum edge-degree of the graphs is at least 2r ² ? 3r + 1. This improves on the cubic bound that follows from the corresponding finite characterization result in 8].