Comparability graph: Difference between revisions

Revision as of 05:25, 7 April 2011

Latest revision as of 07:00, 10 May 2025

(44 intermediate revisions by 25 users not shown)

Line 1:

{{Short description|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 [[comparability|comparable]] to each other in a [[partial order]]. Comparability graphs have also been called '''transitively orientable graphs''', '''partially orderable graphs''', and '''containment graphs'''.,<ref>{{harvtxt|Golumbic|1980}}, p. 105; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 94.</ref> and '''divisor graphs'''.{{sfnp|Chartrand|Muntean|Saenpholphat|Zhang|2001}}

An '''incomparability graph''' is an [[undirected graph]] that connects pairs of elements that are not [[comparability|comparable]] to each other in a [[partial order]].

==Definitions and characterization==

[[ImageFile:ForbiddenPoset intervalet subgraphgraphe de comparabilité.svg|thumb|One300px|Hasse diagram of thea forbiddenposet induced(left) subgraphsand of aits comparability graph. The generalized cycle (right)]]

''[[Image:Forbidden interval subgraph.svg|thumb|One of the forbidden induced subgraphs of a''–''b''–''d''–''f''–''d''–''c''–''e''–''c''–''b''–''a'' comparability graph. The generalized cycle {{mvar|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 partial order|strict partially ordered set]] (''S'',&lt;), the '''comparability graph''' of (''S'', &lt;) 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'' &lt; ''v''. That is, for a partially ordered set, take the [[directed acyclic graph]], apply [[transitive closure]], and remove orientation.

For any [[strict partial order|strict partially ordered set]] {{math|(''S'',&lt;<)}}, the '''comparability graph''' of {{math|(''S'', &lt;<)}} is the graph {{math|(''S'', ⊥)}} of which the vertices are the elements of ''{{mvar|S''}} and the edges are those pairs {{math|{''u'', ''v''} }} of elements such that {{math|''u'' &lt;< ''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''',<ref>{{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.</ref> an assignment of directions to the edges of the graph such that the [[adjacency relation]] of the resulting [[directed graph]] is [[transitive relation|transitive]]: whenever there exist directed edges (''x'',''y'') and (''y'',''z''), there must exist an edge (''x'',''z'').

Equivalently, a comparability graph is a graph that has a '''transitive orientation''',<ref>{{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.</ref> an assignment of directions to the edges of the graph (i.e. an [[Orientation (graph theory)|orientation]] of the graph) such that the [[adjacency relation]] of the resulting [[directed graph]] is [[transitive relation|transitive]]: whenever there exist directed edges {{math|(''x'',''y'')}} and {{math|(''y'',''z'')}}, there must exist an edge {{math|(''x'',''z'')}}.

One can represent any partial order as a family of sets, such that ''x'' &lt; ''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.<ref>{{harvtxt|Urrutia|1989}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, section 6.3, pp. 94–96.</ref>

One can represent any finite partial order as a family of sets, such that {{math|''x'' &lt;< ''y''}} in the partial order whenever the set corresponding to ''{{mvar|x''}} is a subset of the set corresponding to ''{{mvar|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.<ref>{{harvtxt|Urrutia|1989}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, section 6.3, pp. 94–96.</ref>

Alternatively<ref>{{harvtxt|Ghouila-Houri|1962}} and {{harvtxt|Gilmore|Hoffman|1964}}. See also {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.1.1, p. 91.</ref>, a comparability graph is a graph such that, for every ''generalized 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''. In this context, a generalized cycle is defined to be a [[Glossary of graph theory#Walks|closed walk]] that uses each edge of the graph at most once in each direction.

Alternatively, one can represent the partial order by a family of [[integer]]s, such that {{math|''x'' < ''y''}} whenever the integer corresponding to {{mvar|x}} is a [[divisor]] of the integer corresponding to {{mvar|y}}. Because of this construction, comparability graphs have also been called divisor graphs.{{sfnp|Chartrand|Muntean|Saenpholphat|Zhang|2001}}

Comparability graphs can be characterized as the graphs such that, for every ''generalized cycle'' (see below) of odd length, one can find an edge {{math|(''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 [[Glossary of graph theory#Walks|closed walk]] that uses each edge of the graph at most once in each direction.<ref>{{harvtxt|Ghouila-Houri|1962}} and {{harvtxt|Gilmore|Hoffman|1964}}. See also {{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.1.1, p. 91.</ref> Comparability graphs can also be characterized by a list of [[forbidden induced subgraph]]s.<ref>{{harvtxt|Gallai|1967}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 91 and p. 112.</ref>

==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 {{harvtxt|Seymour|2006}} observes, every comparability graph that is neither complete nor bipartite has a [[skew partition]].

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 (graph theory)|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.<ref>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.</ref>

Line 26:

[[Cograph]]s can be characterized as the comparability graphs of [[series-parallel partial order]]s; thus, cographs are also comparability graphs.<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, corollary 6.4.1, p. 96; {{harvtxt|Jung|1978}}.</ref>

[[Threshold graph]]s are another special kind of comparability graph.

Every comparability graph is [[perfect graph|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.<ref>{{harvtxt|Golumbic|1980}}, theorems 5.34 and 5.35, p. 133. See also the proof in the [[Dilworth's theorem]] article.</ref> More specifically, comparability graphs are [[perfectly orderable graph]]s, a subclass of perfect graphs: a [[greedy coloring]] algorithm for a [[topological ordering]] of a transitive orientation of the graph will optimally color them.<ref>{{harvtxt|Maffray|2003}}.</ref>

Every comparability graph is [[perfect graph|perfect]]. The perfection of comparability graphs canis be[[Mirsky's seentheorem]], asand athe dual formperfection of their complements is [[Dilworth's theorem]],; andthese this factfacts, together with the complementation property of [[perfect graphsgraph theorem]] can be used to prove Dilworth's theorem itselffrom Mirsky's theorem or vice versa.<ref>{{harvtxt|Golumbic|1980}}, theorems 5.34 and 5.35, p. 133. See also the proof in the [[Dilworth's theorem]] article.</ref> More specifically, comparability graphs are [[perfectly orderable graph]]s, a subclass of perfect graphs: a [[greedy coloring]] algorithm for a [[topological ordering]] of a transitive orientation of the graph will optimally color them.<ref>{{harvtxt|Maffray|2003}}.</ref>

The [[complement graph|complement]] of every comparability graph is a [[string graph]].<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|20092012}}.</ref>

==Algorithms==

A transitive orientation of a graph, if it exists, can be found in linear time.<ref>{{harvtxt|McConnell|Spinrad|1997}}; see {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p. 91.</ref> 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 computedsolved in polynomial time for comparability graphs.

==See also==

*[[Bound graph]], a different graph defined from a partial order

==Notes==

{{reflist|230em}}

== References ==

{{refbegin|230em}}

*{{citation | last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt | last2 = Le | first2 = Van Bang | last3 = Spinrad | first3 = Jeremy | title = Graph Classes: A Survey | publisher = SIAM Monographs on Discrete Mathematics and Applications | year = 1999 | isbn = 0-89871-432-X | url-access = registration | url = https://archive.org/details/graphclassessurv0000bran }}.

*{{citation

| last1 = BrandstädtChartrand | first1 = AndreasGary | last2author1-link = LeGary | first2 = Van Bang | last3 = Spinrad | first3 = JeremyChartrand

| titlelast2 = GraphMuntean Classes:| Afirst2 Survey= Raluca

| last3 = Saenpholphat | first3 = Varaporn

| publisher = SIAM Monographs on Discrete Mathematics and Applications

| last4 = Zhang | first4 = Ping | author4-link = Ping Zhang (graph theorist)

| year = 1999

| department = Proceedings of the Thirty-Second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001)

| isbn = 0-89871-432-X}}.

| journal = Congressus Numerantium

| mr = 1887439

| pages = 539–548189–200

| title = Which graphs are divisor graphs?

| volume = 16151

| year = 2001}}

*{{citation

| last1 = Dushnik | first1 = Ben | last2 = Miller | first2 = E. W.

Line 53 ⟶ 65:

| year = 1941

| pages = 600–610

| id = {{MathSciNet | idmr = 0004862}}

| doi = 10.2307/2371374

| issue = 3

| publisher = The Johns Hopkins University Press

| jstor = 2371374}}| hdl = 10338.dmlcz/100377

| hdl-access = free

}}.

*{{citation

| first1 = J.Jacob | last1 = Fox | first2 = J.Jànos | last2 = Pach | author2-link = János Pach

| title = String graphs and incomparability graphs

| journal = Canadian[[Advances Journal ofin Mathematics]]

| url = http://www.princeton.edu/~jacobfox/papers/stringpartial071709.pdf

| yearvolume = 2009}}.230

| issue = 3

| year = 19992012

| doi = 10.1016/j.aim.2012.03.011

| doi-access = free

| url = http://www.princetonrenyi.eduhu/~jacobfoxpach/paperspublications/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

| id = {{MathSciNet | idmr = 0221974}}

| doi = 10.1007/BF02020961}}.| s2cid = 119485995

}}.

*{{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

| id = {{MathSciNet | id = 0175811}}

| doi = 10.4153/CJM-1964-055-5}}.

*{{citation

| last = Ghouila-Houri | first = Alain

Line 88 ⟶ 103:

| year = 1962

| pages = 1370–1371

| id = {{MathSciNet | idmr =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 | authorlinkauthor-link = Martin Charles Golumbic

| title = Algorithmic Graph Theory and Perfect Graphs

| publisher = Academic Press

Line 96 ⟶ 121:

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

Line 112 ⟶ 137:

| issue = 2

| pages = 125–133

| id = {{MathSciNet | idmr = 0491356}}

| doi = 10.1016/0095-8956(78)90013-8}}.| doi-access = free

}}.

*{{citation

| first = L. | last = Lovász | authorlinkauthor-link = László Lovász

| contribution = Perfect graphs

| title = Selected Topics in Graph Theory

Line 127 ⟶ 153:

| 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

Line 134 ⟶ 160:

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

Line 142 ⟶ 169:

| pages = 19–25}}.

*{{citation

| last = TrotterSeymour | first = WilliamPaul T.| 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

| title chapter= Partial orders and Euclidean geometry

| booktitletitle = Algorithms and Order

| editor = [[Ivan Rival|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 }}.

{{refend}}

[[Category:{{Order theory]]}}

[[Category:Graph families]]

[[Category:Order theory]]

[[Category:Perfect graphs]]