Weak perfect graph theorem

The weak perfect graph theorem (or just perfect graph theorem and theorem by Lovász ) is a mathematical theorem from graph theory , which deals with structures that occur when corner coloring. It was first proven in 1972 by László Lovász .

"A graph G is perfect if and only if its complementary graph G ^{c is} perfect."

In the following, denote for a graph G its vertex set, one of induced subgraphs , the chromatic number , the clique number , the stability number and the correlation number . ${\displaystyle V}$ ${\displaystyle G_{A}}$ ${\displaystyle A\subset V}$ ${\displaystyle \chi (G)}$ ${\displaystyle \omega (G)}$ ${\displaystyle \alpha (G)}$ ${\displaystyle k(G)}$

The following conditions are then (formally) equivalent:

1. ${\displaystyle \chi (G_{A})=\omega (G_{A})}$for everyone (G perfect). ${\displaystyle A\subseteq V}$
2. ${\displaystyle k(G_{A})=\alpha (G_{A})}$for everyone (G ^c perfect). ${\displaystyle A\subseteq V}$
3. ${\displaystyle \alpha (G_{A})\omega (G_{A})\geq |A|}$for everyone . ${\displaystyle A\subseteq V}$

literature

• Reinhard Diestel: graph theory . Springer 2006, ISBN 3-540-21391-0 , sentence 4.5.4

Web links

• Eric W. Weisstein : Perfect Graph Theorem . In: MathWorld (English).