The concept of a bounded tolerance order

A set of real intervals {Iν | ν ∈ V} can be viewed as a representation of the interval graph G = (V, E) where xy ∈ E ⇔ Ix ∩ Iy ≠ Ø. It can also be interpreted as representing an interval order P = (V, ≺) where x ≺ y if and only if Ix is completely to the left of Iy (which we denote Ix ≪ Iy). The graph G and the order P are related in that G is the incomparability graph of P, that is, xy ∈ E(G) ⇔ x ∥ y in P. Thus, results about interval graphs have counterparts in the world of ordered sets. For example, note the similarity in the characterization theorems below.

Theorem 5.1.(Gilmore and Hoffman, 1964) A graph G is an interval graph if and only if it is a cocomparability graph with no induced C4.

Theorem 5.2.(Fishburn, 1970) An order P is an interval order if and only if it has no induced2 + 2.

The graph C4 is the incomparability graph of the order 2 + 2, so the same 4-element structure is forbidden in both theorems. Theorem 5.1 has the extra condition that G be a cocomparability graph. This is not needed in Theorem 5.2 since the relation in any ordered set is transitive, and thus the incomparability graph of any ordered set is always a cocomparability graph.