Remote Access Proceedings of the American Mathematical Society
Green Open Access

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

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?)

  • [1] M. Aigner and G. Prins, Uniquely partially orderable graphs, J. London Math. Soc. (2) 3 (1971), 260-266. MR 43 #1866. MR 0276118 (43:1866)
  • [2] G. Birkhoff, Lattice theory, 3rd ed., Amer. Math. Soc. Colloq. Publ., vol. 25, Amer. Math. Soc., Providence, R.I., 1967. MR 37 #2638. MR 0227053 (37:2638)
  • [3] B. Dushnik and E. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600-610. MR 3, 73. MR 0004862 (3:73a)
  • [4] S. Even, A. Pnueli and A. Lempel, Permutation graphs and transtive graphs, J. Assoc. Comput. Mach. 19 (1972), 400-410. MR 47 #1675. MR 0313120 (47:1675)
  • [5] A. Ghouila-Houri, Caractérisation des graphes non orientés dont on peut orienter les arêtes de manière à obtenir le graphe d'une relation d'ordre, C. R. Acad. Sci. Paris 254 (1962), 1370-1371. MR 30 #2495. MR 0172275 (30:2495)
  • [6] P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad J. Math. 16 (1964), 539-548. MR 31 #87. MR 0175811 (31:87)
  • [7] M. C. Golumbic, Comparability graphs and a new matroid, Ph.D Thesis, Columbia Univ., New York, 1975. MR 0406867 (53:10653)
  • [8] T. Hiraguchi, On the dimension of partially ordered sets, Sci. Rep. Kanazawa Univ. 1 (1951), 77-94. MR 17, 19. MR 0070681 (17:19g)
  • [9] G. Sabidussi, Graph derivatives, Math. Z. 76 (1961), 385-401. MR 24 #A53. MR 0130186 (24:A53)
  • [10] W. T. Trotter, Inequalities in dimension theory for posets, Proc. Amer. Math. Soc. 47 (1975), 311-316. MR 0369192 (51:5427)

Similar Articles

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

Retrieve articles in all journals with MSC: 06A10

Additional Information

Keywords: Comparability graph, poset, dimension
Article copyright: © Copyright 1976 American Mathematical Society

American Mathematical Society