Any transitive orientation of the edges of a comparability graph G = (V, E) gives an ordered set P = (V, ≺), and we say that G is the comparability graph of P. A graph can have many different transitive orientations, so there may be many different orders with the same comparability graph. In Figure 7.1, orders P, Q, and R (and their duals) all have the comparability graph G shown, and they represent all six transitive orientations of G. Determining the number of transitive orientations of a comparability graph was studied by Shevrin and Filippov (1970) and Golumbic (1977) (see also Section 5.3 of Golumbic, 1980).

Interval orders illustrate an interesting invariance property. If G has a transitive orientation F which gives an interval order P, then every transitive orientation of G gives an interval order. This can be seen as follows. Since P has an interval representation, this same representation demonstrates that G is an interval graph. Suppose F′ is another transitive orientation of G whose ordered set P′ is not an interval order. Then P′ must contain a 2 + 2 (Theorem 1.6) in which case G contains an induced C4, a contradiction (Theorem 1.3).

In this chapter, we investigate a variety of order-theoretic properties and parameters which exhibit this kind of invariance. We present a standard technique for proving invariance based on a theorem of Gallai, and illustrate its use on the dimension of an order. We then turn our attention to tolerance properties.