Comparability graph: Difference between revisions

Revision as of 04:40, 21 February 2016

Revision as of 23:35, 29 September 2017

Line 28:

[[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[[perfect property of perfectgraph graphstheorem]] 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|2012}}.</ref>