|
For larger values of k > 2, there are infinitely many minimal forbidden induced subgraphs. This does not rule out either the existence of polynomial recognition or the possibility of forbidden subgraph characterization (similar to Beineke's) of particular families of graphs. For r=1 there are very interesting results available for k-uniform hypergraphs, k > 2 by various graph theorists. The difficulty in finding a characterization of r-intersection graphs is twofold. First, there are infinitely many minimal forbidden subgraphs, even for k=3. For m > 0, consider a chain of m diamonds (figure 1) such that consecutive diamonds share vertices of degree two. Second, many authors have suggested that there is no "Krausz-style" characterization in terms fo clique covers, for k > 2. For k > 2, let us add pendent edges at every vertex of degree 2 or 4 is one family of minimal forbidden graphs for k > 2.
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 [34], 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 [47], 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. BotheBoth the results ofin Rao in[47] imply polynomial recognition algorithms for garphs under the corresponding minimum degree and minimum edge-degree conditions.
In [56] Metelsky and Tyshkevich, gave the finite forbidden subgraph characterization for linear k-uniform hypergraphs with minimum degree at least 19 in G anlogous to [7].
==References==
* 1. Berge , C., Hypergraphs, Combinatorics of Finite sets. Amsterdam: North-Holland 1989.
* 2. Bermond, J.C., Heydemann, M.C., Sotteau, D.: Line graphs of hypergraphs I. Discrete Math. 18 235-241 (1977).
* 3. Heydemann, M. C., Scotteau, D,: Line graphs of hypergraphs II. Colloq. MAth. Soc. J. Bolyai 18, 567-582 (1976)
* 4. M S. Jacobson, Andre E. Kezdy, and Jeno Lehel: Recognizing Intersection Graphs of Linear Uniform Hypergraphs. Graphs and Combinatorics (1977) 13: 359-367.
* 5. J. Krausz, Demonstration nouvelle d'un theorem de Whitney sur les reseaux, Mat. Fiz. Lapok 50 (1943) pp. 75-89
6. Yury Metelsky and Regina Tyshkevich, On Line graphs of Linear 3-uniform Hypergraphs: J. of Graph Theory 25, 243-251 (1997).
7.
| 