✦ LIBER ✦
Comparability graphs with constraint, partial semi-orders and interval orders
✍ Scribed by Claude Flament
- Publisher
- Elsevier Science
- Year
- 1985
- Tongue
- English
- Weight
- 580 KB
- Volume
- 53
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
A symmetric, anfireflexive relation S is a comparability graph ff 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.