×

A characterization of uniquely representable interval graphs. (English) Zbl 0588.05045

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.
Reviewer: L.Niepel

MSC:

05C99 Graph theory
06A06 Partial orders, general
Full Text: DOI

References:

[1] Hanlon, P., Counting interval graphs, Trans. Amer. Math. Soc., 272, 426 (1982) · Zbl 0519.05039
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.