{"history":[],"article":{"id":"7a3a01e7-dcce-4cd4-b532-0851d7827099","title":"Comparability graph","slug":"comparability-graph","content":":::summary\n:::\n\n# \nIn [graph theory](https://bliptext.com/articles/graph-theory), a **comparability graph** is an [undirected graph](https://bliptext.com/articles/undirected-graph) that connects pairs of elements that are [comparable](https://bliptext.com/articles/comparability) to each other in a [partial order](https://bliptext.com/articles/partial-order).\nComparability graphs have also been called **transitively orientable graphs**, **partially orderable graphs**, **containment graphs**, and **divisor graphs**.\nAn **incomparability graph** is an [undirected graph](https://bliptext.com/articles/undirected-graph) that connects pairs of elements that are not [comparable](https://bliptext.com/articles/comparability) to each other in a [partial order](https://bliptext.com/articles/partial-order).\n\n# Definitions and characterization\nFor any [strict partially ordered set](https://bliptext.com/articles/strict-partial-order)\n(S,<)\n, the **comparability graph** of\n(S, <)\nis the graph\n(S, ⊥)\nof which the vertices are the elements of S and the edges are those pairs\n{u, v}\nof elements such that\nu < v\n. That is, for a partially ordered set, take the [directed acyclic graph](https://bliptext.com/articles/directed-acyclic-graph), apply [transitive closure](https://bliptext.com/articles/transitive-closure), and remove orientation.\nEquivalently, a comparability graph is a graph that has a **[transitive](https://bliptext.com/articles/transitive-relation) [orientation](https://bliptext.com/articles/orientation-graph-theory)**, an assignment of directions to the edges of the graph (i.e. an [orientation](https://bliptext.com/articles/orientation-graph-theory) of the graph) such that the [adjacency relation](https://bliptext.com/articles/adjacency-relation) of the resulting [directed graph](https://bliptext.com/articles/directed-graph) is [transitive](https://bliptext.com/articles/transitive-relation): whenever there exist directed edges\n(x,y)\nand\n(y,z)\n, there must exist an edge\n(x,z)\n.\nOne can represent any finite partial order as a family of sets, such that\nx < y\nin 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.\nAlternatively, one can represent the partial order by a family of [integers](https://bliptext.com/articles/integer), such that\nx < y\nwhenever the integer corresponding to x is a [divisor](https://bliptext.com/articles/divisor) of the integer corresponding to y. Because of this construction, comparability graphs have also been called [divisor](https://bliptext.com/articles/divisor) graphs.\nComparability graphs can be characterized as the graphs such that, for every generalized cycle (see below) of odd length, one can find an edge\n(x,y)\nconnecting two vertices that are at distance two in the cycle.\nSuch an edge is called a triangular chord.\nIn this context, a generalized cycle is defined to be a [closed walk](https://bliptext.com/articles/glossary-of-graph-theory) that uses each edge of the graph at most once in each direction.\nComparability graphs can also be characterized by a list of [forbidden induced subgraphs](https://bliptext.com/articles/forbidden-induced-subgraph).\n# [Hasse diagram of a poset (left) and its comparability graph (right) | upload.wikimedia.org/wikipedia/commons/2/29/Poset///et///graphe///de///comparabilit%C3%A9.svg]\n# [One of the forbidden induced subgraphs of a comparability graph. The generalized cycle a–b–d–f–d–c–e–c–b–a in this graph has odd length (nine) but has no triangular chords. | upload.wikimedia.org/wikipedia/commons/e/e2/Forbidden///interval///subgraph.svg]\n\n# Relation to other graph families\nEvery [complete graph](https://bliptext.com/articles/complete-graph) is a comparability graph, the comparability graph of a [total order](https://bliptext.com/articles/total-order).\nAll acyclic orientations of a complete graph are transitive.\nEvery [bipartite graph](https://bliptext.com/articles/bipartite-graph) is also a comparability graph.\nOrienting 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.\nAs observes, every comparability graph that is neither complete nor bipartite has a [skew partition](https://bliptext.com/articles/skew-partition).\nThe [complement](https://bliptext.com/articles/complement-graph-theory) of any [interval graph](https://bliptext.com/articles/interval-graph) is a comparability graph.\nThe comparability relation is called an [interval order](https://bliptext.com/articles/interval-order).\nInterval graphs are exactly the graphs that are chordal and that have comparability graph complements.\nA [permutation graph](https://bliptext.com/articles/permutation-graph) is a containment graph on a set of intervals.\nTherefore, permutation graphs are another subclass of comparability graphs.\nThe [trivially perfect graphs](https://bliptext.com/articles/trivially-perfect-graph) are the comparability graphs of [rooted trees](https://bliptext.com/articles/rooted-tree).\n[Cographs](https://bliptext.com/articles/cograph) can be characterized as the comparability graphs of [series-parallel partial orders](https://bliptext.com/articles/series-parallel-partial-order); thus, cographs are also comparability graphs.\n[Threshold graphs](https://bliptext.com/articles/threshold-graph) are another special kind of comparability graph.\nEvery comparability graph is [perfect](https://bliptext.com/articles/perfect-graph).\nThe perfection of comparability graphs is [Mirsky's theorem](https://bliptext.com/articles/mirsky-s-theorem), and the perfection of their complements is [Dilworth's theorem](https://bliptext.com/articles/dilworth-s-theorem); these facts, together with the [perfect graph theorem](https://bliptext.com/articles/perfect-graph-theorem) can be used to prove [Dilworth's theorem](https://bliptext.com/articles/dilworth-s-theorem) from [Mirsky's theorem](https://bliptext.com/articles/mirsky-s-theorem) or vice versa.\nMore specifically, comparability graphs are [perfectly orderable graphs](https://bliptext.com/articles/perfectly-orderable-graph), a subclass of perfect graphs: a [greedy coloring](https://bliptext.com/articles/greedy-coloring) algorithm for a [topological ordering](https://bliptext.com/articles/topological-ordering) of a transitive orientation of the graph will optimally color them.\nThe [complement](https://bliptext.com/articles/complement-graph) of every comparability graph is a [string graph](https://bliptext.com/articles/string-graph).\n\n# Algorithms\nA transitive orientation of a graph, if it exists, can be found in linear time.\nHowever, 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](https://bliptext.com/articles/matrix-multiplication).\nBecause comparability graphs are perfect, many problems that are hard on more general classes of graphs, including [graph coloring](https://bliptext.com/articles/graph-coloring) and the [independent set problem](https://bliptext.com/articles/independent-set-problem), can be solved in polynomial time for comparability graphs.","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-26T08:26:25.056Z","updated_at":"2025-01-26T08:26:25.056Z","search_vector":"'compar':1 'graph':2","search_content":" \n \n\n# \nIn [graph theory](https://bliptext.com/articles/graph-theory), a **comparability graph** is an [undirected graph](https://bliptext.com/articles/undirected-graph) that connects pairs of elements that are [comparable](https://bliptext.com/articles/comparability) to each other in a [partial order](https://bliptext.com/articles/partial-order).\nComparability graphs have also been called **transitively orientable graphs**, **partially orderable graphs**, **containment graphs**, and **divisor graphs**.\nAn **incomparability graph** is an [undirected graph](https://bliptext.com/articles/undirected-graph) that connects pairs of elements that are not [comparable](https://bliptext.com/articles/comparability) to each other in a [partial order](https://bliptext.com/articles/partial-order).\n\n# Definitions and characterization\nFor any [strict partially ordered set](https://bliptext.com/articles/strict-partial-order)\n(S,<)\n, the **comparability graph** of\n(S, <)\nis the graph\n(S, ⊥)\nof which the vertices are the elements of S and the edges are those pairs\n{u, v}\nof elements such that\nu < v\n. That is, for a partially ordered set, take the [directed acyclic graph](https://bliptext.com/articles/directed-acyclic-graph), apply [transitive closure](https://bliptext.com/articles/transitive-closure), and remove orientation.\nEquivalently, a comparability graph is a graph that has a **[transitive](https://bliptext.com/articles/transitive-relation) [orientation](https://bliptext.com/articles/orientation-graph-theory)**, an assignment of directions to the edges of the graph (i.e. an [orientation](https://bliptext.com/articles/orientation-graph-theory) of the graph) such that the [adjacency relation](https://bliptext.com/articles/adjacency-relation) of the resulting [directed graph](https://bliptext.com/articles/directed-graph) is [transitive](https://bliptext.com/articles/transitive-relation): whenever there exist directed edges\n(x,y)\nand\n(y,z)\n, there must exist an edge\n(x,z)\n.\nOne can represent any finite partial order as a family of sets, such that\nx < y\nin 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.\nAlternatively, one can represent the partial order by a family of [integers](https://bliptext.com/articles/integer), such that\nx < y\nwhenever the integer corresponding to x is a [divisor](https://bliptext.com/articles/divisor) of the integer corresponding to y. Because of this construction, comparability graphs have also been called [divisor](https://bliptext.com/articles/divisor) graphs.\nComparability graphs can be characterized as the graphs such that, for every generalized cycle (see below) of odd length, one can find an edge\n(x,y)\nconnecting two vertices that are at distance two in the cycle.\nSuch an edge is called a triangular chord.\nIn this context, a generalized cycle is defined to be a [closed walk](https://bliptext.com/articles/glossary-of-graph-theory) that uses each edge of the graph at most once in each direction.\nComparability graphs can also be characterized by a list of [forbidden induced subgraphs](https://bliptext.com/articles/forbidden-induced-subgraph).\n# [Hasse diagram of a poset (left) and its comparability graph (right) | upload.wikimedia.org/wikipedia/commons/2/29/Poset///et///graphe///de///comparabilit%C3%A9.svg]\n# [One of the forbidden induced subgraphs of a comparability graph. The generalized cycle a–b–d–f–d–c–e–c–b–a in this graph has odd length (nine) but has no triangular chords. | upload.wikimedia.org/wikipedia/commons/e/e2/Forbidden///interval///subgraph.svg]\n\n# Relation to other graph families\nEvery [complete graph](https://bliptext.com/articles/complete-graph) is a comparability graph, the comparability graph of a [total order](https://bliptext.com/articles/total-order).\nAll acyclic orientations of a complete graph are transitive.\nEvery [bipartite graph](https://bliptext.com/articles/bipartite-graph) is also a comparability graph.\nOrienting 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.\nAs observes, every comparability graph that is neither complete nor bipartite has a [skew partition](https://bliptext.com/articles/skew-partition).\nThe [complement](https://bliptext.com/articles/complement-graph-theory) of any [interval graph](https://bliptext.com/articles/interval-graph) is a comparability graph.\nThe comparability relation is called an [interval order](https://bliptext.com/articles/interval-order).\nInterval graphs are exactly the graphs that are chordal and that have comparability graph complements.\nA [permutation graph](https://bliptext.com/articles/permutation-graph) is a containment graph on a set of intervals.\nTherefore, permutation graphs are another subclass of comparability graphs.\nThe [trivially perfect graphs](https://bliptext.com/articles/trivially-perfect-graph) are the comparability graphs of [rooted trees](https://bliptext.com/articles/rooted-tree).\n[Cographs](https://bliptext.com/articles/cograph) can be characterized as the comparability graphs of [series-parallel partial orders](https://bliptext.com/articles/series-parallel-partial-order); thus, cographs are also comparability graphs.\n[Threshold graphs](https://bliptext.com/articles/threshold-graph) are another special kind of comparability graph.\nEvery comparability graph is [perfect](https://bliptext.com/articles/perfect-graph).\nThe perfection of comparability graphs is [Mirsky's theorem](https://bliptext.com/articles/mirsky-s-theorem), and the perfection of their complements is [Dilworth's theorem](https://bliptext.com/articles/dilworth-s-theorem); these facts, together with the [perfect graph theorem](https://bliptext.com/articles/perfect-graph-theorem) can be used to prove [Dilworth's theorem](https://bliptext.com/articles/dilworth-s-theorem) from [Mirsky's theorem](https://bliptext.com/articles/mirsky-s-theorem) or vice versa.\nMore specifically, comparability graphs are [perfectly orderable graphs](https://bliptext.com/articles/perfectly-orderable-graph), a subclass of perfect graphs: a [greedy coloring](https://bliptext.com/articles/greedy-coloring) algorithm for a [topological ordering](https://bliptext.com/articles/topological-ordering) of a transitive orientation of the graph will optimally color them.\nThe [complement](https://bliptext.com/articles/complement-graph) of every comparability graph is a [string graph](https://bliptext.com/articles/string-graph).\n\n# Algorithms\nA transitive orientation of a graph, if it exists, can be found in linear time.\nHowever, 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](https://bliptext.com/articles/matrix-multiplication).\nBecause comparability graphs are perfect, many problems that are hard on more general classes of graphs, including [graph coloring](https://bliptext.com/articles/graph-coloring) and the [independent set problem](https://bliptext.com/articles/independent-set-problem), can be solved in polynomial time for comparability graphs.","revisionCount":0},"hasMore":false,"nextCursor":null}

History