The dimension of a comparability graph

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.