A Characterization of Comparability Graphs and of Interval Graphs

Canadian Journal of Mathematics - Tập 16 - Trang 539-548 - 1964
Paul C. Gilmore1, Alan J. Hoffman
1IBM Research Center

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

10.1073/pnas.45.11.1607

Gilmore, 1962, Abstract, Internat. Congress Mathematicians, 29

Ghouilà-Houri, 1962, Caractérisation des graphes nonorientês dont on peut orienter les aretes de manière à obtenir le graphe d'une relation d'ordre, 254, 1370

Hajos, 1957, Über eine Art von Graphen, Intern. Math. Nachr., 11, 65

10.4064/fm-51-1-45-64

10.1090/S0002-9939-1962-0172273-0

Thông tin
Thông tin xuất bản

Canadian Journal of Mathematics

Tập 16

539-548

Thông tin tác giả