Abstract
We prove comparability invariance results for three classes of ordered sets: bounded tolerance orders (equivalent to parallelogram orders), unit bitolerance orders (equivalent to point-core bitolerance orders) and unit tolerance orders (equivalent to 50% tolerance orders). Each proof uses a different technique and relies on the alternate characterization.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arditti, J. C. (1976) Graphes de comparabilité et dimension des ordres, Note de Recherches CRM 607, Centre de Recherche Mathématiques, Université Montréal.
Arditti, J. C. and Jung, H. A. (1980) The dimension of finite and infinite comparability graphs, J. London Math. Soc. 21, 31-38.
Bogart, K., Fishburn, P., Isaak, G. and Langley, L. (1995) Proper and unit tolerance graphs, Discrete Appl. Math. 60, 37-51.
Bogart, K. P. and Isaak, G. (1998) Proper and unit bitolerance orders and graphs, DiscreteMath. 181, 37-51.
Dagan, I., Golumbic, M. C. and Pinter, R. Y. (1988) Trapezoid graphs and their coloring, Discrete Appl. Math. 21, 35-46.
Fishburn, P. C. and Trotter, W. T. (1999) Split semiorders, Discrete Math. 195, 111-126.
Gallai, T. (1967) Transitiv orientierbare graphen, Acta Math. Hungar. 18, 25-66.
Golumbic, M. C. and Monma, C. L. (1982) A generalization of interval graphs with tolerances, Congressus Numerantium 35, 321-331.
Golumbic, M. C. and Trenk, A. N., Tolerance Graphs, monograph in preparation.
Gysin, R. (1977) Dimension transitive orientierbar graphen, Acta Math. Acad. Sci. Hungar. 29, 313-316.
Habib, M. (1984) Comparability invariants, Ann. Discrete Math. 23, 371-386.
Habib, M., Kelly, D. and Möhring, R. (1991) Interval dimension is a comparability invariant, Discrete Appl. Math. 88, 211-229.
Habib, M., Kelly, D. and Möhring, R. (1992) Comparability invariance of geometric notions of order dimension, manuscript.
Kelly, D. (1986) Invariants of finite comparability graphs, Order 3, 155-158.
Langley, L. (June 1993) Interval Tolerance Orders and Dimension, PhD Thesis, Dartmouth College.
Trotter, W. T. (1992) Combinatorics and Partially Ordered Sets, Johns Hopkins University Press, Baltimore, MD.
Trotter, W. T., Moore, J. I. and Sumner, D. (1976) The dimension of a comparability graph, Discrete Math. 16, 361-381.
Niederle, J. (2000) Being a proper trapezoid ordered set is a comparability invariant, Order 17, 301-308.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bogart, K.P., Laison, J.D., Isaak, G. et al. Comparability Invariance Results for Tolerance Orders. Order 18, 281–294 (2001). https://doi.org/10.1023/A:1012291815365
Issue Date:
DOI: https://doi.org/10.1023/A:1012291815365