Revision as of 10:42, 23 October 2008 edit 78.92.183.162 (talk) →References ← Previous edit		Revision as of 10:43, 23 October 2008 edit undo 78.92.183.162 (talk) →Line graphs of k-uniform hypergraphs, k ≥ 3 Next edit →
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 subgraphs. (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\|~~Lóvász~~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}}.

Line graph of a hypergraph: Difference between revisions