Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

The dimension of a comparability graph


Authors: W. T. Trotter, John I. Moore and David P. Sumner
Journal: Proc. Amer. Math. Soc. 60 (1976), 35-38
MSC: Primary 06A10
MathSciNet review: 0417001
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 06A10

Retrieve articles in all journals with MSC: 06A10


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9939-1976-0417001-6
PII: S 0002-9939(1976)0417001-6
Keywords: Comparability graph, poset, dimension
Article copyright: © Copyright 1976 American Mathematical Society