Dilworth's Theorem - Perfection of Comparability Graphs

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.