Line graph of a hypergraph: Difference between revisions

Revision as of 00:37, 9 March 2008

Revision as of 03:29, 9 March 2008

Line 1:

==Linear Intersection (Line) graphs of k-uniform Hypergraphs[[Hypergraph]] ==

A hypergraph is '''linear''' if any two edges have at most one common vertex. Two edges are '''r-intersecting''' if they share at least r common vertices. '''A k-uniform''' hypergraph is a hypegraph with each edge of size k. Note that simple graphs are linear 2-uniform hypergraphs (a simple graph is loopless and contains no multiple edges). The intersection graph of a graph is usually called as [[Line graph]]. The characterization of [[Line graphsgraph]] was solved by Van Rooij and Wilf and by Beineke. Beineke's (finite) forbidden subgraph characterization immediately implies a polynomial algorithm to recognize line graphs.

For larger values of k > 2, there are infinitely many minimal forbidden induced subgraphs. This does not rule out either the existence of polynomial recognition or the possibility of forbidden subgraph characterization (similar to Beineke's) of particular families of graphs. For r=1 there are very interesting results available for k-uniform hypergraphs, k > 2 by various graph theorists.