Content deleted Content added
m convert special characters (via WP:JWB) |
|||
Line 5:
A hypergraph is '''linear''' if each pair of hyperedges intersects in at most one vertex. Every graph is the line graph, not only of some hypergraph, but of some linear hypergraph {{harv|Berge|1989}}.
==Line graphs of ''k''-uniform hypergraphs, ''k''
{{harvtxt|Beineke|1968}} characterized line graphs of graphs by a list of 9 [[forbidden induced subgraph]]s. (See the article on [[line graph]]s.) No characterization by forbidden induced subgraphs is known of line graphs of k-uniform hypergraphs for any ''k'' ≥ 3, and {{harvtxt|Lovász|1977}} showed there is no such characterization by a finite list if ''k'' = 3.
Line 11:
{{harvtxt|Krausz|1943}} characterized line graphs of graphs in terms of [[clique (graph theory)|clique]] covers. (See [[Line graph#Characterization and recognition|Line Graphs]].) A global characterization of Krausz type for the line graphs of ''k''-uniform hypergraphs for any ''k'' ≥ 3 was given by {{harvtxt|Berge|1989}}.
==Line graphs of ''k''-uniform linear hypergraphs, ''k''
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.
| |||