Almost all comparability graphs are UPO

Rolf H. Möhring

Type: Article

Publication Date: 1984-01-01

Citations: 18

DOI: https://doi.org/10.1016/0012-365x(84)90035-9

View Publication

Locations

Discrete Mathematics - View

Similar Works

Action	Title	Year	Authors
+	Comparability graphs	2004	Martin Charles Golumbic
+ PDF Chat	Comparability digraphs: An analogue of comparability graphs	2023	Xiaolu Gao Jing Huang Shou‐Jun Xu
+	Polyhedral aspects of partial orders and comparability graphs	1999	Samuel Fiorini
+	Grid Intersection Graphs and Order Dimension	2015	Steven Chaplick Stefan Felsner Udo Hoffmann Veit Wiechert
+	Grid Intersection Graphs and Order Dimension	2015	Steven Chaplick Stefan Felsner Udo Hoffmann Veit Wiechert
+ PDF Chat	The Dimension of a Comparability Graph	1976	W. T. Trotter John I. Moore David P. Sumner
+	MINIMAL NUMBER OF COMPARISONS OF ONE KIND OF PARTIAL ORDERED GRAPHS	1979	培德陈
+	Comparability Graphs	1980	Martin Charles Golumbic
+	Comparability Graphs	1985	David Kelly
+	The number of partial order graphs	1972	Kim Ki-Hang Butler
+	THE PARTIAL ORDER OF GRAPHS AND HOMOMORPHISMS	2004	Pavol Hell Jaroslav Nešetřil
+	Perfectly Ordered Graphs	1984	Vašek Chvátal
+	On Comparability Graphs: Theory and Applications	2015	M. Sivakumar
+ PDF Chat	A Class of Graphs	1960	Paul A. Kelly David Merriell
+	Comparability Invariants	1984	Michel Habib
+	A note on perfect orders	1989	Chı́nh T. Hoàng N.V.R. Mahadev
+ PDF Chat	Optimal labelling schemes for adjacency, comparability, and reachability	2021	Marthe Bonamy Louis Esperet Carla Groenland Alex Scott
+ PDF Chat	Turán-Type Results for Complete h-Partite Graphs in Comparability and Incomparability Graphs	2016	István Tomon
+	Isomorphism Classes of Vertex-Transitive Tournaments	2023	Stefan Zetzsche
+	Almost rank three graphs	1992	A. Gardiner

Works That Cite This (12)

Action	Title	Year	Authors
+	(α, β)-Modules in Graphs.	2021	Michel Habib Lalla Mouatadid Éric Sopena Mengchuan Zou
+	\(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs	2024	Michel Habib Lalla Mouatadid Éric Sopena Mengchuan Zou
+ PDF Chat	Largest Eigenvalue of the Laplacian Matrix: Its Eigenspace and Transitive Orientations	2016	Benjamin Iriarte
+	Comparability Graphs	1985	David Kelly
+	Enumeration of Ordered Sets	1989	Mohamed H. El-Zahar
+	Largest Eigenvalue of the Laplacian Matrix: Its Eigenspace and Transitive Orientations	2016	Benjamin Iriarte Giraldo
+	Combinatorics of acyclic orientations of graphs : algebra, geometry and probability	2015	Benjamin Iriarte Giraldo
+	Largest Eigenvalue of the Laplacian Matrix	2015	Benjamin Iriarte Giraldo
+	A tight lower bound for primitivity in k-structures	1994	Paola Bonizzoni
+	Phase transitions in the evolution of partially ordered sets	1999	Anuschirawan Ralf Taraz

Works Cited by This (5)

Action	Title	Year	Authors
+	Properties of almost all graphs and complexes	1979	Andreas Blass Frank Harary
+	A Fast Algorithm for the Decomposition of Graphs and Posets	1983	Hermann Buer Rolf H. Möhring
+	Asymptotic enumeration of partial orders on a finite set	1975	Daniel J. Kleitman Bruce Rothschild
+ PDF Chat	Uniquely Partially Orderable Graphs	1971	Martin Aigner Geert Prins
+ PDF Chat	The Dimension of a Comparability Graph	1976	W. T. Trotter John I. Moore David P. Sumner