Comparability graph
From Wikipedia, the free encyclopedia
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are related to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, and containment graphs.[1]
Contents |
[edit] Definitions and characterization
If (S,<) is a partial order, one can define an undirected graph in which the vertices are the elements of S and in which there exists an undirected edge connecting any pair of vertices (x,y) such that either x < y or y < x. Such a graph is called a comparability graph.
Equivalently, a comparability graph is a graph that has a transitive orientation.[2] Such an orientation consists of an assignment of a direction to each edge of the graph such that the resulting directed graph satisfies a transitive law: 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.[3]
Alternatively[4], a comparability graph is a graph such that, for every 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.
Comparability graphs can also be characterized by a list of forbidden induced subgraphs.[5]
[edit] Relation to other graph families
Any complete graph 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.[6]
A permutation graph is a containment graph on a set of intervals.[7] Therefore, permutation graphs are another subclass of comparability graphs.
Cographs can be characterized as the comparability graphs of series-parallel partial orders; thus, cographs are also comparability graphs.[8]
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.[9]
[edit] Algorithms
A transitive orientation of a graph, if it exists, can be found in linear time.[10] 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.
As a consequence of their being 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.
[edit] Footnotes
- ^ Golumbic (1980), p. 105; Brändstadt (1999), p. 94.
- ^ Ghuila-Houri (1962); see Brandstädt et al. (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.
- ^ Urrutia (1989); Trotter (1992); Brandstädt et al. (1999), section 6.3, pp. 94–96.
- ^ Ghuila-Houri (1962) and Gilmore and Hoffman (1964). See also Brandstädt et al. (1999), theorem 6.1.1, p. 91.
- ^ Gallai (1967); Trotter (1992); Brandstädt et al. (1999), p. 91 and p. 112.
- ^ Transitive orientability of interval graph complements was proven by Ghouila-Houri (1962); the characterization of interval graphs is due to Gilmore and Hoffman (1964). See also Golumbic (1980), prop. 1.3, pp. 15–16.
- ^ Dushnik and Miller (1941). Brändstadt et al. (1999), theorem 6.3.1, p. 95.
- ^ Brändstadt et al. (1999), corollary 6.4.1, p. 96; Jung [635].
- ^ Golombic (1980), theorems 5.34 and 5.35, p. 133. See also the proof in the Dilworth's theorem article.
- ^ McConnell and Spinrad (1997); see Brändstadt et al. (1999), p. 91.
[edit] References
- Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999). Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. ISBN 0-89871-432-X.
- Dushnik, Ben; Miller, E. W. (1941). "Partially ordered sets". American Journal of Mathematics 63: 600–610. doi:. MR0004862.
- Gallai, Tibor (1967). "Transitiv orientierbare Graphen". Acta Math. Acad. Sci. Hung. 18: 25–66. doi:. MR0221974.
- Gilmore, P. C.; Hoffman, A. J. (1964). "A characterization of comparability graphs and of interval graphs". Canadian Journal of Mathematics 16: 539–548. MR0175811.
- Ghouila-Houri, Alain (1962). "Caractérization des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre". Les Comptes rendus de l'Académie des sciences 254: 1370–1371. MR0172275.
- Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-12-289260-7.
- Jung, H. A. (1978). "On a class of posets and the corresponding comparability graphs". Journal of Combinatorial Theory, Series B 24 (2): 125–133. doi:. MR0491356.
- McConnell, R. M.; Spinrad, J. (1997). "Linear-time transitive orientation". 8th ACM-SIAM Symposium on Discrete Algorithms: 19–25.
- Trotter, William T. (1992). Combinatorics and Partially Ordered Sets — Dimension Theory. Johns Hopkins University Press.
- Urrutia, Jorge (1989). "Partial orders and Euclidean geometry". Rival, I. (Ed.) Algorithms and Order: 327–436, Kluwer Academic Publishers.
