Interval graph

Interval graph --- интервальный граф.

1. An interval graph is a graph for which one can associate with each vertex an interval on the real line such that two vertices are adjacent if and only if their corresponding intervals have a nonempty intersection.

The following characterization of an interval graph was found by P.C. Gilmore and A.J. Hoffman in 1964.

Theorem. The following statements are equivalent:

(1) [math]\displaystyle{ G }[/math] is an interval graph,

(2) [math]\displaystyle{ G }[/math] is chordal and its complement [math]\displaystyle{ \bar{G} }[/math] is a comparability graph,

(3) there is an interval ordering of the maximal cliques of [math]\displaystyle{ G }[/math].

The interval graphs are an important subclass of the chordal graphs. It is known that a graph [math]\displaystyle{ G }[/math] with [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ m }[/math] edges can be tested for being an interval graph in [math]\displaystyle{ {\mathcal O}(n + m) }[/math].

2. 1-derived graph of a given cf-graph is called an interval graph. Another name is Derived graph.