A characterization of comparability graphs and of interval graphs

PC Gilmore, AJ Hoffman - Canadian Journal of Mathematics, 1964 - cambridge.org
PC Gilmore, AJ Hoffman
Canadian Journal of Mathematics, 1964cambridge.org
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 …
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.
Cambridge University Press