Linear Intersection (Line) graphs of k-uniform 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 graph 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. A characterization of Line graphs in terms of Clique covers is given by J. Krausz. In Rooij and Wilf's proof, the notion of even and odd triangles was introduced to characterize line graphs. A tringle in a graph is called even if every vertex of the graph G is adjecent to either 0 or 2 vertices, otherwise the triangle is called odd.
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.
References
- Berge , C., Hypergraphs, Combinatorics of Finite sets. Amsterdam: North-Holland 1989
- Bermond, J.C., Heydemann, M.C., Sotteau, D.: Line graphs of hypergraphs I. Discrete Math. 18 235-241 (1977)
- Heydemann, M. C., Scotteau, D,: Line graphs of hypergraphs II. Colloq. MAth. Soc. J. Bolyai 18, 567-582 (1976)
- M S. Jacobson, Andre E. Kezdy, and Jeno Lehel: Recognizing Intersection Graphs of Linear Uniform Hypergraphs. Graphs and Combinatorics (1977) 13: 359-367
- J. Krausz, Demonstration nouvelle d'un theorem de Whitney sur les reseaux, Mat. Fiz. Lapok 50 (1943) pp. 75-89