Content deleted Content added
Tangi-tamma (talk | contribs) |
Tangi-tamma (talk | contribs) |
||
Line 6:
Rao, Singhi, Shrikhande proved the surprising result in [7] that there exists a finite family of forbidden graphs for characterizing graphs with minimum degree at least 69 which are intersection graphs of linear 3-uniform hypergraphs. In [4], Jacobson improved the minimum degree condition to 19 and gave a polynomial algorithm to decide whether a graph is a linear intersection graph of 3-uniform hypergraph. The algorithm follows from a simple recursive characterization of graphs of liner Intersection grpahs of k-uniform hypergraphs and relies on the fact that there is a polynomial time recognition algorithm for members of Line graphs of graphs. The complexity of recognizing members of intersection graphs of linear 3-uniform hypergraphs without any minimum degree constraint is not known.
In progress...
In [7], Rao obtained parallel results for any k > 2 under the additional condition that k<sup>3</sup> -2k<sup>2</sup> + 1 is a lower bound on the 'edge-degree of the graph. Define the edge-degree of the edge uv in G as the sum of the degrees of the vertices u and v in G. Both the results in [7] imply polynomial recognition algorithms for garphs under the corresponding minimum degree and minimum edge-degree conditions.
| |||