Interval graph

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. Interval graphs are chordal graphs and perfect graphs. They can be recognized in linear time, and an optimal graph coloring or maximum clique in these graphs can be found in linear time. The interval graphs include all proper interval graphs, graphs defined in the same way from a set of unit intervals. These graphs have been used to model food webs, and to study scheduling problems in which one must select a subset of tasks to be performed at non-overlapping times. Other applications include assembling contiguous subsequences in DNA mapping, and temporal reasoning. An interval graph is an undirected graph G formed from a family of intervals by creating one vertex v_i for each interval S_i, and connecting two vertices v_i and v_j by an edge whenever the corresponding two sets have a nonempty intersection. That is, the edge set of G is It is the intersection graph of the intervals. Three vertices form an asteroidal triple (AT) in a graph if, for each two, there exists a path containing those two but no neighbor of the third. A graph is AT-free if it has no asteroidal triple. The earliest characterization of interval graphs seems to be the following: A graph is an interval graph if and only if it is chordal and AT-free. Other characterizations: A graph is an interval graph if and only if its maximal cliques can be ordered such that each vertex that belongs to two of these cliques also belongs to all cliques between them in the ordering. That is, for every with , it is also the case that whenever . A graph is an interval graph if and only if it does not contain the cycle graph as an induced subgraph and is the complement of a comparability graph. Various other characterizations of interval graphs and variants have been described.