Line graph of a hypergraph: Difference between revisions

Content deleted Content added
Tangi-tamma (talk | contribs)
The new result in the topic have been added.
Line 13:
==Line graphs of ''k''-uniform linear hypergraphs, ''k'' ≥ 3==
 
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. At last {{harvtxt|Skums|Suzdal'|Tyshkevich|2005}} reduced this bound to 16. {{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 [[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