A Characterization of Comparability Graphs and of Interval Graphs
- 1 January 1964
- journal article
- Published by Canadian Mathematical Society in Canadian Journal of Mathematics
- Vol. 16, 539-548
- https://doi.org/10.4153/cjm-1964-055-5
Abstract
Let < be a non-reflexive partial ordering defined on a set P. Let G(P, <) be the undirected graph whose vertices are the elements of P, and whose edges (a, b) connect vertices for which either a < b or b < a. A graph G with vertices P for which there exists a partial ordering < such that G = G(P, <) is called a comparability graph.In §2 we state and prove a characterization of those graphs, finite or infinite, which are comparability graphs. Another proof of the same characterization has been given in (2), and a related question examined in (6). Our proof of the sufficiency of the characterization yields a very simple algorithm for directing all the edges of a comparability graph in such a way that the resulting graph partially orders its vertices.Keywords
This publication has 3 references indexed in Scilit:
- Representation of a finite graph by a set of intervals on the real lineFundamenta Mathematicae, 1962
- The comparability graph of a treeProceedings of the American Mathematical Society, 1962
- ON THE TOPOLOGY OF THE GENETIC FINE STRUCTUREProceedings of the National Academy of Sciences of the United States of America, 1959