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)
“Our children do not want models of perfection, neither do they want us to be buddies, friends, or confidants who never rise above their own levels of maturity and experience. We need to walk that middle ground between perfection and peerage, between intense meddling and apathy—the middle ground where our values, standards, and expectations can be shared with our children.”
—Neil Kurshan (20th century)