Content deleted Content added
→Relation to other graph families: Ce. and add threshold graphs. |
|||
Line 25:
The [[trivially perfect graph]]s are the comparability graphs of [[rooted tree]]s.<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, theorem 6.6.1, p. 99.</ref>
[[Cograph]]s can be characterized as the comparability graphs of [[series-parallel partial order]]s; thus, cographs are also comparability graphs.<ref>{{harvtxt|Brandstädt|Le|Spinrad|1999}}, corollary 6.4.1, p. 96; {{harvtxt|Jung|1978}}.</ref>
[[Threshold graph]]s are another special kind of comparability graph.
Every comparability graph is [[perfect graph|perfect]]. The perfection of comparability graphs is [[Mirsky's theorem]], and the perfection of their complements is [[Dilworth's theorem]]; these facts, together with the complementation property of perfect graphs can be used to prove Dilworth's theorem from Mirsky's theorem or vice versa.<ref>{{harvtxt|Golumbic|1980}}, theorems 5.34 and 5.35, p. 133.</ref> More specifically, comparability graphs are [[perfectly orderable graph]]s, a subclass of perfect graphs: a [[greedy coloring]] algorithm for a [[topological ordering]] of a transitive orientation of the graph will optimally color them.<ref>{{harvtxt|Maffray|2003}}.</ref>
The [[complement graph|complement]] of every comparability graph is a [[string graph]].<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2009}}.</ref>
==Algorithms==
| |||