Line graph of a hypergraph

A global characterization of Krausz type for the line graphs of k-uniform hypergraphs for any k ≥ 3 was given by Berge[5] A global characterization of Krausz type for the line graphs of k-uniform linear hypergraphs for any k ≥ 3 was given by Naik, Rao, Shrikhande, and Singhi.

[6] At the same time, they found a finite list of forbidden induced subgraphs for linear 3-uniform hypergraphs with minimum vertex degree at least 69.

Metelsky and Tyshkevich[10] also proved that, if k > 3, no such finite list exists for linear k-uniform hypergraphs, no matter what lower bound is placed on the degree.

The difficulty in finding a characterization of linear k-uniform hypergraphs is due to the fact that there are infinitely many forbidden induced subgraphs.

For k ≥ 3, add pendant edges at every vertex of degree 2 or 4 to get one of the families of minimal forbidden subgraphs of Naik, Rao, Shrikhande, and Singhi[11] as shown here.

There are some interesting characterizations available for line graphs of linear k-uniform hypergraphs due to various authors[12] under constraints on the minimum degree or the minimum edge degree of G. Minimum edge degree at least k3-2k2+1 in Naik, Rao, Shrikhande, and Singhi[13] is reduced to 2k2-3k+1 in Jacobson, Kézdy, and Lehel[14] and Zverovich[15] to characterize line graphs of k-uniform linear hypergraphs for any k ≥ 3.