Comparability graph: Difference between revisions

Revision as of 19:21, 13 January 2021

Latest revision as of 07:00, 10 May 2025

(15 intermediate revisions by 12 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''', '''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==

[[File:Poset et graphe de comparabilité.svg|thumb|300px|Hasse diagram of a poset (left) and its comparability graph (right)]]

[[Image:Forbidden interval subgraph.svg|thumb|One of the forbidden induced subgraphs of 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.]]

''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 (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 (''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 finite 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>

Alternatively, one can represent the partial order by a family of [[integer]]s, such that ''x'' &lt; ''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.{{sfnp|Chartrand|Muntean|Saenpholphat|Zhang|2001}}

Comparability graphsOne can berepresent characterizedany asfinite thepartial graphsorder suchas that,a for every ''generalized cycle''family of odd lengthsets, onesuch canthat find an edge ({{math|''x'', < ''y'')}} connectingin twothe verticespartial thatorder arewhenever atthe distanceset twocorresponding into the{{mvar|x}} cycle.is Sucha ansubset edgeof isthe calledset acorresponding ''triangularto chord''{{mvar|y}}. In this contextway, acomparability generalizedgraphs cyclecan isbe definedshown to be aequivalent [[Glossaryto ofcontainment graphgraphs theory#Walks|closedof walk]]set families; that usesis, eacha edgegraph ofwith thea graphvertex atfor mosteach onceset in eachthe direction.<ref>{{harvtxt|Ghouila-Houri|1962}}family and {{harvtxt|Gilmore|Hoffman|1964}}.an Seeedge alsobetween {{harvtxt|Brandstädt|Le|Spinrad|1999}},two theoremsets 6.1.1,whenever p.one 91.</ref> Comparability graphs can also be characterized byis a listsubset of [[forbidden inducedthe subgraph]]sother.<ref>{{harvtxt|GallaiUrrutia|19671989}}; {{harvtxt|Trotter|1992}}; {{harvtxt|Brandstädt|Le|Spinrad|1999}}, p.section 91 and6.3, ppp. 11294–96.</ref>

Alternatively, one can represent the partial order by a family of [[integer]]s, such that {{math|''x'' &lt;< ''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==

Line 34 ⟶ 35:

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

Line 47 ⟶ 51:

| last3 = Saenpholphat | first3 = Varaporn

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

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

| journal = Congressus Numerantium

| mr = 1887439

Line 69 ⟶ 73:

}}.

*{{citation

| first1 = J.Jacob | last1 = Fox | first2 = J.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

Line 86 ⟶ 91:

| volume = 18

| year = 1967

| issue = 1–2

| pages = 25–66

| mr = 0221974

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

}}.

*{{citation

| last = Ghouila-Houri | first = Alain

Line 105 ⟶ 112:

| 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

Line 115 ⟶ 123:

| 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

Line 130 ⟶ 138:

| 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

Line 151 ⟶ 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 174 ⟶ 184:

*{{citation

| last = Urrutia | first = Jorge | author-link = Jorge Urrutia Galicia

| title chapter= Partial orders and Euclidean geometry

| book-title = 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]]