The dimension of a comparability graph

Trotter, W. T.; Moore, John I.; Sumner, David P.

doi:10.1090/S0002-9939-1976-0417001-6

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

Martin Aigner and Geert Prins, Uniquely partially orderable graphs, J. London Math. Soc. (2) 3 (1971), 260–266. MR 276118, DOI 10.1112/jlms/s2-3.2.260
Garrett Birkhoff, Lattice theory, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
Ben Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600–610. MR 4862, DOI 10.2307/2371374
S. Even, A. Pnueli, and A. Lempel, Permutation graphs and transitive graphs, J. Assoc. Comput. Mach. 19 (1972), 400–410. MR 313120, DOI 10.1145/321707.321710
Alain 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 (French). MR 172275
P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs, Canadian J. Math. 16 (1964), 539–548. MR 175811, DOI 10.4153/CJM-1964-055-5
Martin Charles Golumbic, Comparability graphs and a new matroid, Proceedings of the Conference on Algebraic Aspects of Combinatorics (Univ. Toronto, Toronto, Ont., 1975) Congressus Numerantium, No. XIII, Utilitas Math., Winnipeg, Man., 1975, pp. 213–217. MR 0406867
Toshio Hiraguchi, On the dimension of partially ordered sets, Sci. Rep. Kanazawa Univ. 1 (1951), 77–94. MR 70681
Gert Sabidussi, Graph derivatives, Math. Z. 76 (1961), 385–401. MR 130186, DOI 10.1007/BF01210984
William T. Trotter Jr., Inequalities in dimension theory for posets, Proc. Amer. Math. Soc. 47 (1975), 311–316. MR 369192, DOI 10.1090/S0002-9939-1975-0369192-2