Perfect graph

Perfect graph --- совершенный граф.

A graph [math]\displaystyle{ G = (V,E) }[/math] is called a perfect graph if the following two conditions are both satisfied: first, the clique number and the chromatic number must be equal for all induced subgraphs, (i.e. [math]\displaystyle{ \omega(G[A]) = \chi(G[A]) }[/math] for all [math]\displaystyle{ A \subseteq V }[/math]), and second, the stability number must equal the clique cover number for all induced subgraphs of [math]\displaystyle{ G }[/math] (i.e., [math]\displaystyle{ \alpha(G[A]) = k(G[A]) }[/math] for all [math]\displaystyle{ A \subseteq V }[/math]). Notice that the two conditions are dual in the sense that a graph satisfies the first condition if and only if its complement satisfies the second. The remarkable fact that a graph satisfies the first equality if and only if it satisfies the second equality was conjectured by C.Berge and proven by L.Lovasz. This is known as the perfect graph theorem.

A near perfect matching in a graph [math]\displaystyle{ G }[/math] is a matching saturating all but one vertex in [math]\displaystyle{ G }[/math].

See also

• Minimal imperfect graph.