Editing Interval graph (section)

{{Short description|Intersection graph for intervals on the real number line}}
{{Distinguish|D-interval hypergraph}}
[[Image:Interval graph.svg|thumb|upright=1.35|Seven intervals on the real line and the corresponding seven-vertex interval graph.]]
In [[graph theory]], an '''interval graph''' is an [[undirected graph]] formed from a set of [[Interval (mathematics)|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 graph]]s and [[perfect graph]]s. 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 graph]]s, graphs defined in the same way from a set of [[unit interval]]s.

These graphs have been used to model [[food web]]s, 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.