Content deleted Content added
see also Bound graph |
Citation bot (talk | contribs) Added isbn. | Use this bot. Report bugs. | Suggested by Abductive | Category:Order theory | #UCB_Category 114/179 |
||
| (2 intermediate revisions by one other user 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 160:
| title = Recent Advances in Algorithms and Combinatorics
| volume = 11
| year = 2003
}}.
*{{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}}
| |||