Comparability graph: Difference between revisions

Revision as of 11:48, 16 March 2025

Latest revision as of 07:00, 10 May 2025

(One intermediate revision by one other user not shown)

Line 1:

{{Short description|Graph linking pairs of comparable elements in a partial order}}

In [[graph theory]] and [[ordervtheoryorder 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 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 189 ⟶ 190:

| publisher = Kluwer Academic Publishers

| pages = 327–436

| doi=10.1007/978-94-009-2639-4| isbn = 978-94-010-7691-3 }}.

{{refend}}