A hypergraph is linear if every two hyperedges share at most one point (Note that every linear hypergraph without hyperedges of cardinality smaller than 2 is simple). Again a Krausz-type characterization is possible:
Again the recognition problem is difficult: Recognizing intersection graphs of 3-uniform linear hypergraphs is NP-complete.
K5-e and the complement of 4K2 are intersection graphs of linear 3-uniform hypergraphs, but K6-e and the complement of 5K2 are not.The following cruical lemma (compare the analogue for line graphs), follows by the classification of cliques in intersection graphs of 3-uniform hypergraphs. However, there is also a simpler proof:
[NRSS82],
[JKL97],
[HK97],
[MT97],
Every clique with more than k2-k+1
vertices in the intersection graph G
of a k-uniform linear simple hypergraph
H is a star graph.
|
Proof:
Assume the hyperedges X1, X2,...,
Xn with n > k(k-1)+1
in a linear hypergraph are pairwise intersecting.
By the pigeon-hole principle,
some point a of X1 is covered by at
least k of the sets
X2,...,Xn, say a
 X2,...,
aXk+1.
Every Xi, k+1 < i
 n, not containg
a has to intersect
X1, X2,...,Xk+1
in different points,
this is impossible since |Xi|= k.
Thus all Xi contain a. |
Therefore, other than in the general case, in the linear case all large enough cliques of the intersection graph must be star cliques. Then we can achieve polynomiality for the recognition problem by restricting the possible models:
For every k  3,
let H be the class of k-uniform linear
hypergraphs where every point lies in at least k2-k+2 hyperedges.
Then intersection graphs of members of H
can be recognized
in polynomial time.
|
However, it is always more desirable to get a characterization under additional assumptions on the graph, not on the model. This is possible for k=3: In [NRSS82] it has been shown that it is possible to test graphs of minimum degree at least 69 whether or not they are intersection graphs of linear 3-uniform hypergraphs. The bound has recently independently been lowered to 19 by a different approach by two groups [JKL97] and [MT97]. Even a bound of 14 is possible:
|
[MPST*]:
There is some polynomial-time algorithm that tests graphs of
minimum degree at least 14 whether or not they are
intersection graphs of linear 3-uniform hypergraphs.
|
|
Sketch of the proof for minimum degree 19:
[JKL97]
[MT97]
So assume G is the intersection graph of some linear
3-uniform hypergraph, and assume
Every vertex lying in one or two of these already revealed star cliques gets 2 respectively 1 as a label. Next we delete all edges in the the revealed star cliques. Every vertex that lied in three of them should be isolated now, and is also deleted. For the resulting vertex-labeled graph G´ we check whether it is the intersection graph of some linear hypergraph where every Sx should have as many elements (1 or 2) as the label of x indicates. This is essentially recognition of line graphs, compare [JKL97] and [MT97], and can be done in linear time. |
Note that this approach is not extendable to higher k.
Back to the start page for intersection graphs.
(G)