Comparability graph
Encyclopedia
In graph 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, and containment graphs.
For any strict partially ordered set (S,<), the comparability graph of (S, <) is the graph (S, ⊥) of which the vertices are the elements of S and the edges are those pairs {u, v} of elements such that u < v. That is, for a partially ordered set, take the directed acyclic graph
, apply transitive closure
, and remove orientation.
Equivalently, a comparability graph is a graph that has a transitive orientation, an assignment of directions to the edges of the graph such that the adjacency relation of the resulting directed graph
is transitive
: whenever there exist directed edges (x,y) and (y,z), there must exist an edge (x,z).
One can represent any partial order as a family of sets, such that x < y in the partial order whenever the set corresponding to x is a subset of the set corresponding to y. In this way, comparability graphs can be shown to be equivalent to containment graphs of set families; that is, a graph with a vertex for each set in the family and an edge between two sets whenever one is a subset of the other.
Alternatively, a comparability graph is a graph such that, for every generalized cycle of odd length, one can find an edge (x,y) connecting two vertices that are at distance two in the cycle. Such an edge is called a triangular chord. In this context, a generalized cycle is defined to be a closed walk that uses each edge of the graph at most once in each direction.
Comparability graphs can also be characterized by a list of forbidden induced subgraphs.
is a comparability graph, as any acyclic orientation of a complete graph is transitive.
Any bipartite graph
is also a comparability graph. Orienting the edges of a bipartite graph from one side of the bipartition to the other results in a transitive orientation.
The complement of any interval graph
is a comparability graph. The comparability relation is called an interval order
. Interval graphs are exactly the graphs that are chordal and that have comparability graph complements.
A permutation graph
is a containment graph on a set of intervals. Therefore, permutation graphs are another subclass of comparability graphs.
The trivially perfect graphs are the comparability graphs of rooted trees.
Cograph
s can be characterized as the comparability graphs of series-parallel partial order
s; thus, cographs are also comparability graphs.
Every comparability graph is perfect
. The perfection of comparability graphs can be seen as a dual form of Dilworth's theorem
, and this fact together with the complementation property of perfect graphs can be used to prove Dilworth's theorem itself. More specifically, comparability graphs are perfectly orderable graphs, a subclass of perfect graphs: a greedy coloring
algorithm for a topological ordering of a transitive orientation of the graph will optimally color them.
The complement graph
of every comparability graph is a string graph
.
.
Because comparability graphs are perfect, many problems that are hard on more general classes of graphs, including graph coloring
and the independent set problem, can be computed in polynomial time for comparability graphs.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a comparability graph is an undirected graph that connects pairs of elements that are comparable
Comparability
In mathematics, any two elements x and y of a set P that is partially ordered by a binary relation ≤ are comparable when either x ≤ y or y ≤ x...
to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, and containment graphs.
Definitions and characterization
Directed acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
, apply transitive closure
Transitive closure
In mathematics, the transitive closure of a binary relation R on a set X is the transitive relation R+ on set X such that R+ contains R and R+ is minimal . If the binary relation itself is transitive, then the transitive closure will be that same binary relation; otherwise, the transitive closure...
, and remove orientation.
Equivalently, a comparability graph is a graph that has a transitive orientation, an assignment of directions to the edges of the graph such that the adjacency relation of the resulting directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
is transitive
Transitive relation
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b, and b is in turn related to an element c, then a is also related to c....
: whenever there exist directed edges (x,y) and (y,z), there must exist an edge (x,z).
One can represent any partial order as a family of sets, such that x < y in the partial order whenever the set corresponding to x is a subset of the set corresponding to y. In this way, comparability graphs can be shown to be equivalent to containment graphs of set families; that is, a graph with a vertex for each set in the family and an edge between two sets whenever one is a subset of the other.
Alternatively, a comparability graph is a graph such that, for every generalized cycle of odd length, one can find an edge (x,y) connecting two vertices that are at distance two in the cycle. Such an edge is called a triangular chord. In this context, a generalized cycle is defined to be a closed walk that uses each edge of the graph at most once in each direction.
Comparability graphs can also be characterized by a list of forbidden induced subgraphs.
Relation to other graph families
Any complete graphComplete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
is a comparability graph, as any acyclic orientation of a complete graph is transitive.
Any bipartite graph
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
is also a comparability graph. Orienting the edges of a bipartite graph from one side of the bipartition to the other results in a transitive orientation.
The complement of any interval graph
Interval graph
In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
is a comparability graph. The comparability relation is called an interval order
Interval order
In mathematics, especially order theory,the interval order for a collection of intervals on the real lineis the partial order corresponding to their left-to-right precedence relation—one interval, I1, being considered less than another, I2, if I1 is completely to the left of I2.More formally, a...
. Interval graphs are exactly the graphs that are chordal and that have comparability graph complements.
A permutation graph
Permutation graph
In areas of mathematics influenced by graph theory, a permutation graph is the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane...
is a containment graph on a set of intervals. Therefore, permutation graphs are another subclass of comparability graphs.
The trivially perfect graphs are the comparability graphs of rooted trees.
Cograph
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
s can be characterized as the comparability graphs of series-parallel partial order
Series-parallel partial order
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations....
s; thus, cographs are also comparability graphs.
Every comparability graph is perfect
Perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
. The perfection of comparability graphs can be seen as a dual form of Dilworth's theorem
Dilworth's theorem
In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem characterizes the width of any finite partially ordered set in terms of a partition of the order into a minimum number of chains...
, and this fact together with the complementation property of perfect graphs can be used to prove Dilworth's theorem itself. More specifically, comparability graphs are perfectly orderable graphs, a subclass of perfect graphs: a greedy coloring
Greedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color...
algorithm for a topological ordering of a transitive orientation of the graph will optimally color them.
The complement graph
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of every comparability graph is a string graph
String graph
In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the...
.
Algorithms
A transitive orientation of a graph, if it exists, can be found in linear time. However, the algorithm for doing so will assign orientations to the edges of any graph, so to complete the task of testing whether a graph is a comparability graph, one must test whether the resulting orientation is transitive, a problem provably equivalent in complexity to matrix multiplicationMatrix multiplication
In mathematics, matrix multiplication is a binary operation that takes a pair of matrices, and produces another matrix. If A is an n-by-m matrix and B is an m-by-p matrix, the result AB of their multiplication is an n-by-p matrix defined only if the number of columns m of the left matrix A is the...
.
Because comparability graphs are perfect, many problems that are hard on more general classes of graphs, including graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
and the independent set problem, can be computed in polynomial time for comparability graphs.