Suppose we have graph $G =(V, E)$ that $V(G) = {a, b, c, d, e}$ and $E(G) = {ab, ad, bc, be, cd, de} $
How should I know if this is an interval graph or not?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
This is not a interval graph since we have the edges $ab$ $ad$ $cb$ and $cd$ but we do not have $ac$ or $bd$.
Why this leads to a contradiction: Assume that it is an interval graph. This means that the intervals $b$ and $d$ have empty intersection so the intervals are disjoint. But the interval $a$ intersects both $b$ and $d$. Meaning that since $a$ is an interval it has to bridge at least the 'gap' between $b$ and $d$. We can say the same about $c$. Meaning that $a$ and $c$ have that 'gap' in common. This would mean that $ac$ has to be an edge. But it is not. Thus is not an interval graph.
$\begingroup$
$\endgroup$
There are linear algorithms for recognizing interval graphs (Using PQ-trees or Lex BFS). But here it is convenient to use its forbidden graph characterization.
You can check this yourself: A interval graph cannot have an induced cycle of length greater than 3. (On trying to build a cycle on $n$ intervals, you always end up with the complete graph $K_n$.) There also are a few more classes of minimal forbidden induced graphs for interval graphs, which you can try to figure out.
As you can see your graph has an induced cycle of length $4$, hence it is not an interval graph.