Chapter 8
Interval graphs
Martin Charles Golumbic
Publisher Summary
This chapter presents the characterizations of interval graphs. It also presents several theorems and its corollary, where the class of interval graphs belongs in the world of perfect graphs. One of theorems discussed is on “G” as an undirected graph. The following statements are equivalent: (1) G is an interval graph; (2) G contains no chord less 4-cycle and its complement G is a comparability graph; (3) the maximal cliques of G can be linearly ordered such that, for every vertex x of G, the maximal cliques containing x occur consecutively.” Another theorem proved is “an undirected graph G is an interval graph if and only if its clique matrix M has the consecutive 1's property for ...
