A Characterization of Comparability Graphs and of Interval Graphs

1964/01/01 by Paul C. Gilmore, Alan J. Hoffman · 23 citations
Computer Science · Mathematics · #semigroups and automata theory #Advanced Graph Theory Research #Formal Methods in Verification #Mathematics #Comparability #Combinatorics #Comparability graph #Discrete mathematics #Interval graph #Characterization (materials science) #Graph #Pathwidth #Line graph

paper · pdf · doi:10.4153/cjm-1964-055-5

openalex publication_date 1964/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

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.

Cited by

• On the pathwidth of chordal graphs
• Treewidth of cocomparability graphs and a new order-theoretic parameter
• Approximating treewidth and pathwidth of some classes of perfect graphs
• Tree-width and path-width of comparability graphs of interval orders
• Adjacency labelling for proper minor-closed graph classes
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The LBFS Structure and Recognition of Interval Graphs
• On maximal independent sets of vertices in claw-free graphs
• On a class of posets and the corresponding comparability graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Classes of perfect graphs
• A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular‐arc graphs, and nested interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• On the coloration of perfect graphs
• A Consistent Extension of Condorcet’s Election Principle
• Weakly closed graphs and F-purity of binomial edge ideals
• Fast parallel algorithms for chordal graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Transitiv orientierbare Graphen
• Comparability graphs and intersection graphs
• Comparability graph [wikipedia]
• Interval graph [wikipedia]