Ingraph theory andorder theory, acomparability graph is anundirected graph that connects pairs of elements that arecomparable to each other in apartial order. Comparability graphs have also been calledtransitively orientable graphs,partially orderable graphs,containment graphs,[1] anddivisor graphs.[2]Anincomparability graph is anundirected graph that connects pairs of elements that are notcomparable to each other in apartial order.
For anystrict partially ordered set(S,<), thecomparability graph of(S, <) is the graph(S, ⊥) of which the vertices are the elements ofS and the edges are those pairs{u,v} of elements such thatu <v. That is, for a partially ordered set, take thedirected acyclic graph, applytransitive closure, and remove orientation.
Equivalently, a comparability graph is a graph that has atransitive orientation,[3] an assignment of directions to the edges of the graph (i.e. anorientation of the graph) such that theadjacency relation of the resultingdirected graph istransitive: whenever there exist directed edges(x,y) and(y,z), there must exist an edge(x,z).
One can represent any finite partial order as a family of sets, such thatx <y in the partial order whenever the set corresponding tox is a subset of the set corresponding toy. 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.[4]Alternatively, one can represent the partial order by a family ofintegers, such thatx <y whenever the integer corresponding tox is adivisor of the integer corresponding toy. Because of this construction, comparability graphs have also been called divisor graphs.[2]
Comparability graphs can be characterized as the graphs such that, for everygeneralized cycle (see below) 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 atriangular chord. In this context, a generalized cycle is defined to be aclosed walk that uses each edge of the graph at most once in each direction.[5] Comparability graphs can also be characterized by a list offorbidden induced subgraphs.[6]
Acocomparability graph is thecomplement of a comparability graph. That is, given a comparability graphG = (V,E), its cocomparability graphG̅ = (V,E̅) has the same vertex set but complementary edge set: two vertices are adjacent inG̅ if and only if they are not adjacent inG.
Cocomparability graphs are precisely the intersection graphs of continuous curves between two parallel lines, or equivalently, the intersection graphs of intervals on two parallel lines.[7] A graph is a cocomparability graph if and only if its complement admits a transitive orientation.
Cocomparability graphs form an important subclass ofperfect graphs, inheriting this property from the fact that both comparability graphs and their complements are perfect (byDilworth's theorem andMirsky's theorem respectively).[8]
Every cocomparability graph isasteroidal triple-free (AT-free).[9] This places them within the hierarchy:interval ⊂permutation ⊂trapezoid ⊂ cocomparability ⊂AT-free.
The class of cocomparability graphs is self-complementary in the sense that the complement of a cocomparability graph is a comparability graph, and vice versa.
Interval graphs are exactly the graphs that arechordal and have cocomparability complements; that is, thecomplement of anyinterval graph is a comparability graph, and the comparability relation is called aninterval order.[10]
Cocomparability graphs are a subclass ofstring graphs; thecomplement of every comparability graph is a string graph.[11]
Everycomplete graph is a comparability graph, the comparability graph of atotal order. All acyclic orientations of a complete graph are transitive. Everybipartite 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, corresponding to a partial order of height two. AsSeymour (2006) observes, every comparability graph that is neither complete nor bipartite has askew partition.
Apermutation graph is a containment graph on a set of intervals.[12] Therefore, permutation graphs are another subclass of comparability graphs.
Thetrivially perfect graphs are the comparability graphs ofrooted trees.[13]Cographs can be characterized as the comparability graphs ofseries-parallel partial orders; thus, cographs are also comparability graphs.[14]
Threshold graphs are another special kind of comparability graph.
Every comparability graph isperfect. The perfection of comparability graphs isMirsky's theorem, and the perfection of their complements isDilworth's theorem; these facts, together with theperfect graph theorem can be used to prove Dilworth's theorem from Mirsky's theorem or vice versa.[15] More specifically, comparability graphs areperfectly orderable graphs, a subclass of perfect graphs: agreedy coloring algorithm for atopological ordering of a transitive orientation of the graph will optimally color them.[16]
A transitive orientation of a graph, if it exists, can be found in linear time.[17] 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 tomatrix multiplication.
Because comparability graphs (and cocomparability graphs) are perfect, many problems that are hard on more general classes of graphs, includinggraph coloring and theindependent set problem, can be solved for these graphs in polynomial time.