Content deleted Content added
m Fixed citation wikilink(s) and general fixes, replaced: | journal = Discrete Mathematics → | journal = Discrete Mathematics |
mNo edit summary Tags: Mobile edit Mobile app edit iOS app edit |
||
Line 1:
{{Short description|Graph linking pairs of comparable elements in a partial order}}
In [[graph 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]].
| |||