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:
“These marbles, the works of the dreamers and idealists of old, live on, leading and pointing to good. They are the works of visionaries and dreamers, but they are realizations of soul, the representations of the ideal. They are grand, beautiful, and true, and they speak with a voice that echoes through the ages. Governments have changed; empires have fallen; nations have passed away; but these mute marbles remain—the oracles of time, the perfection of art.”
—Herman Melville (1819–1891)
“Orsino. For women are as roses, whose fair flower
Being once displayed, doth fall that very hour.
Viola. And so they are. Alas, that they are so:
To die even when they to perfection grow.”
—William Shakespeare (1564–1616)