Perfect graph theorem

The perfect graph theorem states: Equivalently, in a perfect graph, the size of the maximum independent set equals the minimum number of cliques in a clique cover.

In n-vertex bipartite graphs, a minimum clique cover takes the form of a maximum matching together with an additional clique for every unmatched vertex, with size n − M, where M is the cardinality of the matching.

Mirsky's theorem characterizing the height of a partially ordered set in terms of partitions into antichains can be formulated as the perfection of the comparability graph of the partially ordered set, and Dilworth's theorem characterizing the width of a partially ordered set in terms of partitions into chains can be formulated as the perfection of the complements of these graphs.

The removed vertices and the new copy of the doubled vertex can then be added back as a single color class, showing that in this case the doubling step leaves the chromatic number unchanged.

The same argument shows that doubling preserves the equality of the clique number and the chromatic number in every induced subgraph of the given graph, so each doubling step preserves the perfection of the graph.

[6] The strong perfect graph theorem of Chudnovsky et al. (2006) states that a graph is perfect if and only if none of its induced subgraphs are cycles of odd length greater than or equal to five, or their complements.