Perfection of Comparability Graphs
A comparability graph is an undirected graph formed from a partial order by creating a vertex per element of the order, and an edge connecting any two comparable elements. Thus, a clique in a comparability graph corresponds to a chain, and an independent set in a comparability graph corresponds to an antichain. Any induced subgraph of a comparability graph is itself a comparability graph, formed from the restriction of the partial order to a subset of its elements.
An undirected graph is perfect if, in every induced subgraph, the chromatic number equals the size of the largest clique. Every comparability graph is perfect: this is essentially just Mirsky's theorem, restated in graph-theoretic terms (Berge & Chvátal 1984). By the perfect graph theorem of Lovász (1972), the complement of any perfect graph is also perfect. Therefore, the complement of any comparability graph is perfect; this is essentially just Dilworth's theorem itself, restated in graph-theoretic terms (Berge & Chvátal 1984). Thus, the complementation property of perfect graphs can provide an alternative proof of Dilworth's theorem.
Read more about this topic: Dilworth's Theorem
Famous quotes containing the words perfection of and/or perfection:
“Perfection of means and confusion of goals seem—in my opinion—to characterize our age.”
—Albert Einstein (1879–1955)
“I would with such perfection govern, sir,
T’excel the golden age.”
—William Shakespeare (1564–1616)