Minimal imperfect graphs: A simple approach (Q1924490)

For a graph \(G\), let \(\omega(G)\) denote the cardinality of a maximum clique of \(G\), and \(\alpha(G)\) the cardinality of a maximum independent set. \textit{L. Lovász} [J. Comb. Theory, Ser. B 13, 95-98 (1972; Zbl 0241.05107)] showed that a graph \(G\) is perfect iff \(|H|\leq \omega(H)\alpha(H)\) for every induced subgraph \(H\) of \(G\). This paper provides a short proof of this theorem, and discusses its consequences.