Editing Perfect graph (section)

{{Short description|Graph with tight clique-coloring relation}}
{{good article}}
[[File:Paley9-unique-triangle.svg|thumb|240px|The graph of the [[3-3 duoprism]] (the [[line graph]] of <math>K_{3,3}</math>) is perfect. Here it is colored with three colors, with one of its 3-vertex maximum cliques highlighted.]]
In [[graph theory]], a '''perfect graph''' is a [[Graph (discrete mathematics)|graph]] in which the [[Graph coloring|chromatic number]] equals the size of the [[maximum clique]], both in the graph itself and in every [[induced subgraph]]. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

The perfect graphs include many important families of graphs and serve to unify results relating [[Graph coloring|colorings]] and cliques in those families. For instance, in all perfect graphs, the [[graph coloring problem]], [[maximum clique problem]], and [[maximum independent set problem]] can all be solved in [[polynomial time]], despite their greater complexity for non-perfect graphs. In addition, several important [[minimax theorem]]s in [[combinatorics]], including [[Dilworth's theorem]] and [[Mirsky's theorem]] on [[partially ordered set]]s, [[Kőnig's theorem (graph theory)|Kőnig's theorem]] on [[Matching (graph theory)|matchings]], and the [[Erdős–Szekeres theorem]] on monotonic sequences, can be expressed in terms of the perfection of certain associated graphs.

The [[perfect graph theorem]] states that the [[complement graph]] of a perfect graph is also perfect. The [[strong perfect graph theorem]] characterizes the perfect graphs in terms of certain [[forbidden graph characterization|forbidden induced subgraphs]], leading to a [[polynomial time algorithm]] for testing whether a graph is perfect.