Editing Perfect graph (section)

==Definitions and characterizations==
[[File:7-hole and antihole.svg|thumb|A seven-vertex cycle and its complement, showing in each case an optimal coloring and a maximum clique (shown with heavy edges). Neither graph uses a number of colors equal to its clique size, so neither is perfect.]]
A [[clique (graph theory)|clique]] in an [[undirected graph]] is a subset of its vertices that are all adjacent to each other, such as the subsets of vertices connected by heavy edges in the illustration. The [[clique number]] is the number of vertices in the largest clique: two in the illustrated seven-vertex cycle, and three in the other graph shown. A [[graph coloring]] assigns a color to each vertex so that each two adjacent vertices have different colors, also shown in the illustration. The [[chromatic number]] of a graph is the minimum number of colors in any coloring. The colorings shown are optimal, so the chromatic number is three for the 7-cycle and four for the other graph shown. The vertices of any clique must have different colors, so the chromatic number is always greater than or equal to the clique number. For some graphs, they are equal; for others, such as the ones shown, they are unequal. The perfect graphs are defined as the graphs for which these two numbers are equal, not just in the graph itself, but in every [[induced subgraph]] obtained by deleting some of its vertices.{{r|crst-2003}}

[[File:Complementary perfect graphs.svg|thumb|upright=1.35|Two complementary perfect graphs]]
The [[perfect graph theorem]] asserts that the [[complement graph]] of a perfect graph is itself perfect. The complement graph has an edge between two vertices if and only if the given graph does not. A clique, in the complement graph, corresponds to an [[independent set (graph theory)|independent set]] in the given. A coloring of the complement graph corresponds to a [[clique cover]], a partition of the vertices of the given graph into cliques. The fact that the complement of a perfect graph <math>G</math> is also perfect implies that, in <math>G</math> itself, the [[independence number]] (the size of its [[maximum independent set]]), equals its [[clique cover number]] (the fewest number of cliques needed in a clique cover). More strongly, the same thing is true in every induced subgraph of the complement graph. This provides an alternative and equivalent definition of the perfect graphs: they are the graphs for which, in each induced subgraph, the independence number equals the clique cover number.{{r|lovasz-1972a|cornuejols-2002}}

The [[strong perfect graph theorem]] gives a different way of defining perfect graphs, by their structure instead of by their properties.
It is based on the existence of [[cycle graph]]s and their complements within a given graph. A cycle of odd length, greater than three, is not perfect: its clique number is two, but its chromatic number is three. By the perfect graph theorem, the complement of an odd cycle of length greater than three is also not perfect. The complement of a length-5 cycle is another length-5 cycle, but for larger odd lengths the complement is not a cycle; it is called an ''anticycle''. The strong perfect graph theorem asserts that these are the only [[forbidden graph characterization|forbidden induced subgraphs]] for the perfect graphs: a graph is perfect if and only if its induced subgraphs include neither an odd cycle  nor an odd anticycle of five or more vertices. In this context, [[induced cycle]]s that are not triangles are called "holes", and their complements are called "antiholes", so the strong perfect graph theorem can be stated more succinctly: a graph is perfect if and only if it has neither an odd hole nor an odd antihole.{{r|crst-2006}}

These results can be combined in another characterization of perfect graphs: they are the graphs for which the product of the clique number and independence number is greater than or equal to the number of vertices, and for which the same is true for all induced subgraphs. Because the statement of this characterization remains invariant under complementation of graphs, it implies the perfect graph theorem. One direction of this characterization follows easily from the original definition of perfect: the number of vertices in any graph equals the sum of the sizes of the color classes in an optimal coloring, and is less than or equal to the number of colors multiplied by the independence number. In a perfect graph, the number of colors equals the clique number, and can be replaced by the clique number in this inequality. The other direction can be proved directly,{{r|lovasz-1972b|gasparyan}} but it also follows from the strong perfect graph theorem: if a graph is not perfect, it contains an odd cycle or its complement, and in these subgraphs the product of the clique number and independence number is one less than the number of vertices.{{r|padberg}}