Line graph of a hypergraph: Difference between revisions

Revision as of 22:39, 14 April 2008

Revision as of 12:57, 20 April 2008

Line 15:

A global characterization of Krausz type for the line graphs of ''k''-uniform linear hypergraphs for any ''k'' ≥ 3 was given by {{harvtxt|Naik|Rao|Shrikhande|Singhi|1980}}. At the same time, they found a finite list of forbidden induced subgraphs for linear 3-uniform hypergraphs with minimum vertex degree at least 69. {{harvtxt|Metelsky|Tyshkevich|1997}} and {{harvtxt|Jacobson|Kézdy|Lehel|1997}} improved this bound to 19. {{harvtxt|Metelsky|Tyshkevich|1997}} also proved that, if ''k'' > 3, no such finite list exists for linear ''k''-uniform hypergraphs, no matter what lower bound is placed on the degree.

The difficulty in finding a characterization of linear ''k''-uniform hypergraphs is due to the fact that there are infinitely many forbidden induced subgraphs. To give examples, for ''m'' > 0, consider a chain of ''m'' diamond graphs such that the consecutive diamonds[[diamond]]s share vertices of degree two. For ''k'' ≥ 3, add pendant edges at every vertex of degree 2 or 4 to get one of the families of minimal forbidden subgraphs of

{{harvs|last1 = Naik|last2 = Rao|last3 = Shrikhande|last4 = Singhi|year = 1980|year2 = 1982|txt = yes}} as shown here. This does not rule out either the existence of a polynomial recognition or the possibility of a forbidden induced subgraph characterization similar to Beineke's of line graphs of graphs.