A characterization of uniquely representable interval graphs (Q1073053)

The author gives a characterization of the interval graphs which can be uniquely represented by an interval order. A graph \(G=(V,I)\) is called interval graph if there exists a mapping F from its vertex set to closed real intervals such that two vertices in G are adjacent iff the corresponding intervals are intersecting. An ordering (V,P) is called interval order if there exists a mapping from V to the set of intervals such that x P \(y\Leftrightarrow \inf F(x)>\sup F(y)\). An interval order (V,P) agrees with an interval graph (V,I) if condition: xy\(\in I\Leftrightarrow xy\not\in P\wedge yx\not\in P\), holds. The graph is called uniquely representable if it agrees with exactly two interval orders. The main result of this note - characterization of these graphs - is given by means of an equivalence defined on edges of the complement of the characterized graph.