Content deleted Content added
Tangi-tamma (talk | contribs) |
Tangi-tamma (talk | contribs) |
||
Line 4:
Let L<sup>k</sup><sub>1</sub> stand for the family of intersection graphs of k-uniform linear hypergraphs. For larger values of k > 2, there are infinitely many minimal forbidden induced subgraphs for L<sup>k</sup><sub>1</sub>. This does not rule out either the existence of polynomial recognition or the possibility of forbidden subgraph characterization (similar to Beineke's) of L<sup>2</sup><sub>1</sub>. There are very interesting results available for L<sup>k</sup><sub>1</sub>, k > 2 by various authors. The difficulty in finding a characterization of L<sup>k</sup><sub>1</sub> 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. For k > 2, let us add pendent edges at every vertex of degree 2 or 4 is one family of minimal forbidden graphs. Second, many authors have suggested that there is no "Krausz-style" characterization in terms of clique covers, for k > 2.
[[Image:
Let d(G) denote the minimum degree of a Graph G. Naik, Rao, Shrikhande and Singhi proved the surprising result in [7, 8] that there exists a finite family of forbidden graphs for characterizing graphs of the family L<sup>k</sup><sub>1</sub> for k=3 with d(g) > 68 . In [4], Jacobson et al. improved the d(G) to 19 and gave a polynomial algorithm to decide whether a graph is a L<sup>k</sup><sub>1</sub> for k=3. The algorithm follows from a simple recursive characterization of L<sup>k</sup><sub>1</sub> and relies on the fact that there is a polynomial time recognition algorithm for members of L<sup>2</sup><sub>1</sub>. Jacboson et al. could not extend finite forbidden subgraph characterization proved in [7] for d(G) > 68 to 19.
| |||