Editing Interval graph (section)

== Characterizations ==

Three independent 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.{{sfnp|Lekkerkerker|Boland|1962}}

Other characterizations:

* A graph is an interval graph if and only if its maximal [[Clique (graph theory)|cliques]] can be ordered <math>M_1,M_2,\dots,M_k</math> 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 <math>v\in M_i\cap M_k</math> with <math>i<k</math>, it is also the case that <math>v\in M_j</math> whenever <math>i<j<k</math>.<ref>{{harvtxt|Fulkerson|Gross|1965}}; {{harvtxt|Fishburn|1985}}</ref>
* A graph is an interval graph if and only if it does not contain the [[cycle graph]] <math>C_4</math> as an [[induced subgraph]] and is the complement of a [[comparability graph]].{{sfnp|Gilmore|Hoffman|1964}}

Various other characterizations of interval graphs and variants have been described.<ref>{{harvtxt|McKee|McMorris|1999}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}</ref>