Comparability graph

Quality 0.50 · 7 views · Updated 2 months ago

Graph linking pairs of comparable elements in a partial order

title: "Comparability graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-families", "order-theory", "perfect-graphs"] description: "Graph linking pairs of comparable elements in a partial order" topic_path: "general/graph-families" source: "https://en.wikipedia.org/wiki/Comparability_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary 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.

Definitions and characterization

::figure[src="https://upload.wikimedia.org/wikipedia/commons/2/29/Poset_et_graphe_de_comparabilité.svg" caption="Hasse diagram of a poset (left) and its comparability graph (right)"] ::

::figure[src="https://upload.wikimedia.org/wikipedia/commons/e/e2/Forbidden_interval_subgraph.svg" caption="a–b–d–f–d–c–e–c–b–a}} in this graph has odd length (nine) but has no triangular chords."] ::

For any strict partially ordered set {{math|(S,

Equivalently, a comparability graph is a graph that has a transitive orientation, an assignment of directions to the edges of the graph (i.e. an orientation 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 finite partial order as a family of sets, such that {{math|x Alternatively, one can represent the partial order by a family of integers, such that {{math|x

Comparability graphs can be characterized as the graphs such that, for every generalized 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 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.

Cocomparability graph

::figure[src="https://upload.wikimedia.org/wikipedia/commons/9/99/Cocomparability_graph.svg" caption="The cocomparability graph (right) of a poset (left)"] ::

A cocomparability graph is the complement of a comparability graph. That is, given a comparability graph , its cocomparability graph has the same vertex set but complementary edge set: two vertices are adjacent in G̅ if and only if they are not adjacent in G.

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. A graph is a cocomparability graph if and only if its complement admits a transitive orientation.

Cocomparability graphs form an important subclass of perfect graphs, inheriting this property from the fact that both comparability graphs and their complements are perfect (by Dilworth's theorem and Mirsky's theorem respectively).

Every cocomparability graph is asteroidal triple-free (AT-free).{{citation | last1 = Golumbic | first1 = Martin Charles | last2 = Monma | first2 = Clyde L. | last3 = Trotter | first3 = William T. Jr. | journal = Discrete Applied Mathematics | pages = 157–170 | title = Tolerance graphs | volume = 9 | issue = 2 | year = 1984 | doi = 10.1016/0166-218X(84)90016-7

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 are chordal and have cocomparability complements; that is, the complement of any interval graph is a comparability graph, and the comparability relation is called an interval order.

Cocomparability graphs are a subclass of string graphs; the complement of every comparability graph is a string graph.

Relation to other graph families

Every complete graph is a comparability graph, the comparability graph of a total order. All acyclic orientations of a complete graph are transitive. Every 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, corresponding to a partial order of height two. As observes, every comparability graph that is neither complete nor bipartite has a skew partition.

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. Cographs can be characterized as the comparability graphs of series-parallel partial orders; thus, cographs are also comparability graphs.

Threshold graphs are another special kind of comparability graph.

Every comparability graph is perfect. The perfection of comparability graphs is Mirsky's theorem, and the perfection of their complements is Dilworth's theorem; these facts, together with the perfect graph theorem can be used to prove Dilworth's theorem from Mirsky's theorem or vice versa. 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.

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 multiplication.

Because comparability graphs (and cocomparability graphs) are perfect, many problems that are hard on more general classes of graphs, including graph coloring and the independent set problem, can be solved for these graphs in polynomial time.

Notes

References

  • .
  • {{citation | last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand | last2 = Muntean | first2 = Raluca | last3 = Saenpholphat | first3 = Varaporn | last4 = Zhang | first4 = Ping | author4-link = Ping Zhang (graph theorist) | department = Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001) | journal = Congressus Numerantium | mr = 1887439 | pages = 189–200 | title = Which graphs are divisor graphs? | volume = 151 | year = 2001}}
  • {{citation | last1 = Dushnik | first1 = Ben | last2 = Miller | first2 = E. W. | title = Partially ordered sets | journal = American Journal of Mathematics | volume = 63 | year = 1941 | pages = 600–610 | mr = 0004862 | doi = 10.2307/2371374 | issue = 3 | publisher = The Johns Hopkins University Press | jstor = 2371374| hdl = 10338.dmlcz/100377 | hdl-access = free
  • {{citation | first1 = Jacob | last1 = Fox | first2 = Jànos | last2 = Pach | author2-link = János Pach | title = String graphs and incomparability graphs | journal = Advances in Mathematics | volume = 230 | issue = 3 | year = 2012 | doi = 10.1016/j.aim.2012.03.011 | doi-access = free | url = http://www.renyi.hu/~pach/publications/stringpartial071709.pdf | pages = 1381–1401
  • {{citation | last = Gallai | first = Tibor | author-link=Tibor Gallai | title = Transitiv orientierbare Graphen | journal = Acta Math. Acad. Sci. Hung. | volume = 18 | year = 1967 | issue = 1–2 | pages = 25–66 | mr = 0221974 | doi = 10.1007/BF02020961| s2cid = 119485995
  • {{citation | last = Ghouila-Houri | first = Alain | title = Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre | journal = Les Comptes rendus de l'Académie des sciences | volume = 254 | year = 1962 | pages = 1370–1371 | mr =0172275}}.
  • {{citation | last1 = Gilmore | first1 = P. C. | last2 = Hoffman | first2 = A. J. | title = A characterization of comparability graphs and of interval graphs | journal = Canadian Journal of Mathematics | volume = 16 | year = 1964 | pages = 539–548 | mr = 0175811 | doi = 10.4153/CJM-1964-055-5| doi-access = free
  • {{citation | last = Golumbic | first = Martin Charles | author-link = Martin Charles Golumbic | title = Algorithmic Graph Theory and Perfect Graphs | publisher = Academic Press | year = 1980 | isbn = 0-12-289260-7}}.
  • {{citation | first1 = M. | last1 = Golumbic | first2 = D. | last2 = Rotem | first3 = J. | last3 = Urrutia | author3-link = Jorge Urrutia Galicia | title = Comparability graphs and intersection graphs | journal = Discrete Mathematics | volume = 43 | year = 1983 | pages = 37–46 | issue = 1 | doi = 10.1016/0012-365X(83)90019-5| doi-access = free}}.
  • {{citation | last = Jung | first = H. A. | title = On a class of posets and the corresponding comparability graphs | journal = Journal of Combinatorial Theory, Series B | volume = 24 | year = 1978 | issue = 2 | pages = 125–133 | mr = 0491356 | doi = 10.1016/0095-8956(78)90013-8| doi-access = free
  • {{citation | first = L. | last = Lovász | author-link = László Lovász | contribution = Perfect graphs | title = Selected Topics in Graph Theory | volume = 2 | publisher = Academic Press | location = London | year = 1983 | pages = 55–87}}.
  • {{citation | last = Maffray | first = Frédéric | contribution = On the coloration of perfect graphs | doi = 10.1007/0-387-22444-0_3 | editor1-last = Reed | editor1-first = Bruce A. | editor1-link = Bruce Reed (mathematician) | editor2-last = Sales | editor2-first = Cláudia L. | pages = 65–84 | publisher = Springer-Verlag | series = CMS Books in Mathematics | title = Recent Advances in Algorithms and Combinatorics | volume = 11 | year = 2003| isbn = 978-1-4684-9268-2
  • {{citation | last1 = McConnell | first1 = R. M. | last2 = Spinrad | first2 = J. | contribution = Linear-time transitive orientation | title = 8th ACM-SIAM Symposium on Discrete Algorithms | year = 1997 | pages = 19–25}}.
  • {{citation | last = Seymour | first = Paul | author-link = Paul Seymour (mathematician) | issue = 109 | journal = Gazette des Mathématiciens | mr = 2245898 | pages = 69–83 | title = How the proof of the strong perfect graph conjecture was found | url = http://users.encs.concordia.ca/~chvatal/perfect/pds.pdf | year = 2006}}.
  • {{citation | last = Trotter | first = William T. | author-link = William T. Trotter | title = Combinatorics and Partially Ordered Sets — Dimension Theory | publisher = Johns Hopkins University Press | year = 1992}}.
  • {{citation | last = Urrutia | first = Jorge | author-link = Jorge Urrutia Galicia | chapter= Partial orders and Euclidean geometry | title = Algorithms and Order | editor = Rival, I. | year = 1989 | publisher = Kluwer Academic Publishers | pages = 327–436 | doi=10.1007/978-94-009-2639-4| isbn = 978-94-010-7691-3 }}.

References

  1. {{harvtxt. Golumbic. 1980, p. 105; {{harvtxt. Brandstädt. Le. Spinrad. 1999, p. 94.
  2. {{harvtxt. Ghouila-Houri. 1962; see {{harvtxt. Brandstädt. Le. Spinrad. 1999, theorem 1.4.1, p. 12. Although the orientations coming from partial orders are [[directed acyclic graph. acyclic]], it is not necessary to include acyclicity as a condition of this characterization.
  3. {{harvtxt. Urrutia. 1989; {{harvtxt. Trotter. 1992; {{harvtxt. Brandstädt. Le. Spinrad. 1999, section 6.3, pp. 94–96.
  4. {{harvtxt. Ghouila-Houri. 1962 and {{harvtxt. Gilmore. Hoffman. 1964. See also {{harvtxt. Brandstädt. Le. Spinrad. 1999, theorem 6.1.1, p. 91.
  5. {{harvtxt. Gallai. 1967; {{harvtxt. Trotter. 1992; {{harvtxt. Brandstädt. Le. Spinrad. 1999, p. 91 and p. 112.
  6. {{harvtxt. Golumbic. Rotem. Urrutia. 1983
  7. {{harvtxt. Golumbic. 1980, theorems 5.34 and 5.35, p. 133.
  8. Transitive orientability of interval graph complements was proven by {{harvtxt. Ghouila-Houri. 1962; the characterization of interval graphs is due to {{harvtxt. Gilmore. Hoffman. 1964. See also {{harvtxt. Golumbic. 1980, prop. 1.3, pp. 15–16.
  9. {{harvtxt. Golumbic. Rotem. Urrutia. 1983 and {{harvtxt. Lovász. 1983. See also {{harvtxt. Fox. Pach. 2012.
  10. {{harvtxt. Dushnik. Miller. 1941. {{harvtxt. Brandstädt. Le. Spinrad. 1999, theorem 6.3.1, p. 95.
  11. {{harvtxt. Brandstädt. Le. Spinrad. 1999, theorem 6.6.1, p. 99.
  12. {{harvtxt. Brandstädt. Le. Spinrad. 1999, corollary 6.4.1, p. 96; {{harvtxt. Jung. 1978.
  13. {{harvtxt. Golumbic. 1980, theorems 5.34 and 5.35, p. 133.
  14. {{harvtxt. Maffray. 2003.
  15. {{harvtxt. McConnell. Spinrad. 1997; see {{harvtxt. Brandstädt. Le. Spinrad. 1999, p. 91.

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::

graph-familiesorder-theoryperfect-graphs