set in terms of partitions into chains can be formulated as the perfection of the complements of these graphs. Thus, the perfect graph theorem can be used to prove Dilworth's theorem from the (much easier) proof of Mirsky's theorem, or vice versa.

Lovász's proof

To prove the perfect graph theorem, Lovász used an operation of replacing vertices in a graph by cliques; it was already known to Berge that, if a graph is perfect, the graph formed by this replacement process is also perfect.

1.Previous
3.Next