Perfect graph

Summary

A perfect graph is a graph in which, for every induced subgraph, the chromatic number equals the size of the largest clique. For every graph the chromatic number is at least the clique number, and perfect graphs are those where this lower bound is always exact. Bipartite graphs, interval graphs and comparability graphs are perfect. The strong perfect graph theorem characterizes perfect graphs by forbidden induced subgraphs. On perfect graphs, colouring and finding a largest clique can be done in polynomial time.