Live briefing
Everything about Comparability graph
Graph linking pairs of comparable elements in a partial order
In graph theory and order theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order. Wikipedia →
🧠Start here: a 6-step reading path
- Read the overview: Comparability graphA 5-minute orientation
- Skim a recent paper: Comparability digraphs: An analogue of comparability graphsInfluential work since 2022
- Pick up a classic book: Algebraic properties of treesThe most-reprinted book on the subject
- Read the landmark paper: The comparability graph of a treeCited 86 times
- Go sideways: Permutation graphA closely related topic
- Go sideways: Trivially perfect graphA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
The comparability graph of a tree
The dimension of a comparability graph
P4-comparability graphs
An interval graph is not a comparability graph
Comparability graph augmentation for some multiprocessor scheduling problems
An interval graph is a comparability graph
A note on “The comparability graph of a tree”
A Note on "The Comparability Graph of a Tree"
🆕 Influential since 2022
đź“š Books worth reading
- 📕Algebraic properties of treesLadislav Nebeský · 1969
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
đź”— Related topics
- Permutation graph In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent…
- Trivially perfect graph In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals…
- Split graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split…
- Chordal bipartite graph In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has…
- Orientation (graph theory) In graph theory, an orientation of an undirected graph is an assignment of a direction to each edge, turning the initial graph into a directed graph. A…
- Perfectly orderable graph In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering…
- Trapezoid graph In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that…
- Distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the distances…