Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
Citation bot (talk | contribs) Added isbn. | Use this bot. Report bugs. | Suggested by Abductive | Category:Order theory | #UCB_Category 114/179 |
||
| (3 intermediate revisions by 2 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 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 157 ⟶ 160:
| title = Recent Advances in Algorithms and Combinatorics
| volume = 11
| year = 2003
}}.
*{{citation
| last1 = McConnell | first1 = R. M. | last2 = Spinrad | first2 = J.
Line 186 ⟶ 190:
| publisher = Kluwer Academic Publishers
| pages = 327–436
| doi=10.1007/978-94-009-2639-4| isbn = 978-94-010-7691-3 }}.
{{refend}}
| |||