Line graph of a hypergraph: Difference between revisions

Revision as of 09:30, 16 September 2009

Revision as of 04:30, 9 February 2010

Line 7:

==Line graphs of ''k''-uniform hypergraphs, ''k'' ≥ 3==

{{harvtxt|Beineke|1968}} characterized line graphs of graphs by a list of 9 [[forbidden induced subgraphssubgraph]]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.

{{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}}.