Revision as of 22:29, 14 April 2008 edit Tangi-tamma (talk \| contribs) 1,091 edits m →Also add the year ← Previous edit		Revision as of 22:39, 14 April 2008 edit undo Tangi-tamma (talk \| contribs) 1,091 edits m →Line graphs of k-uniform linear hypergraphs, k ≥ 3 - Age the findings Next edit →
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}}. ~~They~~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 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

Line graph of a hypergraph: Difference between revisions