A Characterization of Comparability Graphs and of Interval Graphs

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.