In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Is it possible that the join of two intervals graphs is an interval graph?
$\endgroup$ 21 Answer
$\begingroup$Let $G$ and $H$ be two interval graphs. Let's show the join of $G$ and $H$ is an interval graph if and only if one of the two graphs $G$ and $H$ is a complete graph.
Suppose one of the graphs is not a complete graph. Let $u,v$ be a pair of vertices that is not an edge. Because the graph is chordal, it is easy to see that the other graph is the complete graph (otherwise, a missing edge in the other graph would induce $C_4$).
Another way to see it with the intuition of intervals: If an edge is missing in $G$, this implies that there exist two disjoint intervals.
By the definition of a graph join, every interval of $H$ must intersect every interval of $G$, and so must cover the gap between the two disjoint intervals. So all intervals of $H$ intersect each other, hence $H$ is a complete graph.
Every join between a complete graph $G$ and an interval graph $H$ is still an interval graph: Take a set of intervals $S$ describing $H$. We can describe $G$ by a set of intervals that covers every interval in $S$. The union of both sets of intervals gives describes the graph join of $G$ and $H$.
$\endgroup$ 3
