Comparability graph: Difference between revisions

Revision as of 05:23, 4 August 2022

Latest revision as of 07:00, 10 May 2025

(6 intermediate revisions by 5 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]].

Line 14:

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

Line 36:

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.

==See also==

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

==Notes==

Line 109 ⟶ 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 156 ⟶ 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 185 ⟶ 190:

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