Content deleted Content added
Tangi-tamma (talk | contribs) |
Tangi-tamma (talk | contribs) |
||
Line 12:
A hypergraph is '''linear''' if any two edges have at most one common vertex. Two edges are '''r-intersecting''' if they share at least r common vertices. '''A k-uniform''' hypergraph is a hypegraph with each edge of size k. Note that graphs are 2-uniform linear hypergraphs (a simple graph is loopless and contains no multiple edges).
The concept of Line Graphs of graphs
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 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.
| |||