Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The dimension of a comparability graph
HTML articles powered by AMS MathViewer

by W. T. Trotter, John I. Moore and David P. Sumner PDF
Proc. Amer. Math. Soc. 60 (1976), 35-38 Request permission

Abstract:

Dushnik and Miller defined the dimension of a partial order P as the minimum number of linear orders whose intersection is P. Ken Bogart asked if the dimension of a partial order is an invariant of the associated comparability graph. In this paper we answer Bogart’s question in the affirmative. The proof involves a characterization of the class of comparability graphs defined by Aigner and Prins as uniquely partially orderable graphs. Our characterization of uniquely partially orderable graphs is another instance of the frequently encountered phenomenon where the obvious necessary condition is also sufficient.
References
Similar Articles
  • Retrieve articles in Proceedings of the American Mathematical Society with MSC: 06A10
  • Retrieve articles in all journals with MSC: 06A10
Additional Information
  • © Copyright 1976 American Mathematical Society
  • Journal: Proc. Amer. Math. Soc. 60 (1976), 35-38
  • MSC: Primary 06A10
  • DOI: https://doi.org/10.1090/S0002-9939-1976-0417001-6
  • MathSciNet review: 0417001