Comparability graphs with constraint, partial semi-orders and interval orders (Q1068108)

Viewing an undirected graph G without loops or multiple edges as a symmetric, antireflexive relation on a (vertex) set X, one defines G to be a comparability graph, if the edges of G can be assigned a transitive orientation. If C is a sub-relation of S, S is said to be a comparability graph with constraint C, if a transitive orientation for S exists including C. Using the implication classes defined by \textit{M. C. Golumbic} [J. Comb. Theory, Ser. B 22, 68-90 (1977; Zbl 0352.05023)], the author defines an 'implication closure' operation \(\gamma_ S\) on the lattice \({\mathcal R}\) of all binary relations on X and uses it and the transitive closure \(\tau\), to define a superconstraint \(\tau \circ \gamma_ S(C)\) and proves the following theorem: Any implication class of S is antisymmetric and the superconstraint is antisymmetric. A multi- weak order, a partial interval order and a partial semiorder are also defined and some of their properties examined.