Comparability graph

Last updated

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, containment graphs, [1] and divisor graphs. [2] An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

Contents

Definitions and characterization

Hasse diagram of a poset (left) and its comparability graph (right) Poset et graphe de comparabilite.svg
Hasse diagram of a poset (left) and its comparability graph (right)
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. Forbidden interval subgraph.svg
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.

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, [3] 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 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. [4] Alternatively, one can represent the partial order by a family of integers, such that x < y whenever the integer corresponding to x is a divisor of the integer corresponding to y. Because of this construction, comparability graphs have also been called divisor graphs. [2]

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. [5] Comparability graphs can also be characterized by a list of forbidden induced subgraphs. [6]

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 Seymour (2006) observes, every comparability graph that is neither complete nor bipartite has a skew partition.

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. [7]

A permutation graph is a containment graph on a set of intervals. [8] Therefore, permutation graphs are another subclass of comparability graphs.

The trivially perfect graphs are the comparability graphs of rooted trees. [9] Cographs can be characterized as the comparability graphs of series-parallel partial orders; thus, cographs are also comparability graphs. [10]

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. [11] 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. [12]

The complement of every comparability graph is a string graph. [13]

Algorithms

A transitive orientation of a graph, if it exists, can be found in linear time. [14] 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 are perfect, many problems that are hard on more general classes of graphs, including graph coloring and the independent set problem, can be solved in polynomial time for comparability graphs.

Notes

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

Related Research Articles

<span class="mw-page-title-main">Partially ordered set</span> Mathematical set with an ordering

In mathematics, especially order theory, a partially ordered set formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binary relation indicating that, for certain pairs of elements in the set, one of the elements precedes the other in the ordering. The relation itself is called a "partial order."

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Interval graph</span> Intersection graph for intervals on the real number line

In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have .

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

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. It is named for the mathematician Robert P. Dilworth (1950).

<span class="mw-page-title-main">Cograph</span> Graph formed by complementation and disjoint union

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. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

<span class="mw-page-title-main">Split graph</span> Graph which partitions into a clique and independent set

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 graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).

<span class="mw-page-title-main">Distance-hereditary graph</span> Graph whose induced subgraphs preserve distance

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

<span class="mw-page-title-main">Permutation graph</span> Graph representing a permutation

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 pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

<span class="mw-page-title-main">Trivially perfect graph</span> Graph where every connected induced subgraph has a universal vertex

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 the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

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 optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search.

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length in G has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

In mathematics, in the areas of order theory and combinatorics, Mirsky's theorem characterizes the height of any finite partially ordered set in terms of a partition of the order into a minimum number of antichains. It is named for Leon Mirsky (1971) and is closely related to Dilworth's theorem on the widths of partial orders, to the perfection of comparability graphs, to the Gallai–Hasse–Roy–Vitaver theorem relating longest paths and colorings in graphs, and to the Erdős–Szekeres theorem on monotonic subsequences.

<span class="mw-page-title-main">Trapezoid graph</span> Intersection graph of trapezoids between parallel lines

In graph theory, trapezoid graphs are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a trapezoid graph if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, Golumbic, and Pinter in 1988. There exists algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique.

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.

<span class="mw-page-title-main">Acyclic orientation</span>

In graph theory, an acyclic orientation of an undirected graph is an assignment of a direction to each edge that does not form any directed cycle and therefore makes it into a directed acyclic graph. Every graph has an acyclic orientation.

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 a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.