Almost all comparability graphs are UPO

DOI10.1016/0012-365X(84)90035-9zbMath0543.05054MaRDI QIDQ795847

Rolf H. Möhring

Publication date: 1984

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

comparability graphuniquely partially orderable

Mathematics Subject Classification ID

Partial orders, general (06A06) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Related Items

Schedule-induced posets, A \(k\)-structure generalization of the theory of 2-structures, On some complexity properties of N-free posets and posets with bounded decomposition diameter, \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs, A tight lower bound for primitivity in k-structures, Largest Eigenvalue of the Laplacian Matrix: Its Eigenspace and Transitive Orientations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph derivatives
• Partially ordered sets and their comparability graphs
• Properties of almost all graphs and complexes
• A Fast Algorithm for the Decomposition of Graphs and Posets
• The Dimension of Finite and Infinite Comparability Graphs
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Probabilities on finite models
• The Dimension of a Comparability Graph
• Uniquely Partially Orderable Graphs
• A Characterization of Comparability Graphs and of Interval Graphs