Line graph of a hypergraph: Difference between revisions

Revision as of 19:15, 21 March 2008

Revision as of 01:15, 22 March 2008

Line 14:

The concept of Line Graphs of graphs has been extended to Hypergraphs by various authors in [1,2,3].

Let L^k₁ 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^k₁. This does not rule out either the existence of polynomial recognition or the possibility of forbidden subgraph characterization (similar to Beineke's) offor L²₁. There are very interesting results available for L^k₁, k > 2 by various authors. The difficulty in finding a characterization of L^k₁ 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.

<!-- Deleted image removed: [[Image:Hypergraph2.jpeg ]] -->