Comparability graphs with constraint, partial semi-orders and interval orders

AbstractA symmetric, antireflexive relation S is a comparability graph if one can assign a transitive orientation to the edges: we obtain a partial order. We say that S is a comparability graph with constraint C, a subrelation of S, if S has a transitive orientation including C. A characterization is given in terms of antisymmetry of a super-constraint build from C.We study a special case where this super-constraint is a multi-weak order (i.e., a family of weak orders), and apply the results to generalize, in the partial case, the notions of semi-order and of interval order