Perfect Graph - Relation To Min-max Theorems

Relation To Min-max Theorems

In all graphs, the clique number provides a lower bound for the chromatic number, as all vertices in a clique must be assigned distinct colors in any proper coloring. The perfect graphs are those for which this lower bound is tight, not just in the graph itself but in all of its induced subgraphs. For graphs that are not perfect, the chromatic number and clique number can differ; for instance, a cycle of length five requires three colors in any proper coloring but its largest clique has size two.

A proof that a class of graphs is perfect can be seen as a min-max theorem: the minimum number of colors needed for these graphs equals the maximum size of a clique. Many important min-max theorems in combinatorics can be expressed in these terms. For instance, Dilworth's theorem states that the minimum number of chains in a partition of a partially ordered set into chains equals the maximum size of an antichain, and can be rephrased as stating that the complements of comparability graphs are perfect. Mirsky's theorem states that the minimum number of antichains into a partition into antichains equals the maximum size of a chain, and corresponds in the same way to the perfection of comparability graphs.

The perfection of permutation graphs is equivalent to the statement that, in every sequence of ordered elements, the length of the longest decreasing subsequence equals the minimum number of sequences in a partition into increasing subsequences. The Erdős–Szekeres theorem is an easy consequence of this statement.

König's theorem in graph theory states that a minimum vertex cover in a bipartite graph corresponds to a maximum matching, and vice versa; it can be interpreted as the perfection of the complements of bipartite graphs. Another theorem about bipartite graphs, that their chromatic index equals their maximum degree, is equivalent to the perfection of the line graphs of bipartite graphs.