📐 Weak Perfect Graph Theorem

A graph $G$ is perfect if and only if its complement $\\overline{G}$ is perfect.

Proof: A replication lemma shows that if $G$ is perfect, so is any graph obtained by "replicating" vertices. Using this, one shows $G$ perfect implies $\\chi(G) \\cdot \\alpha(G) \\geq n$ for all induced subgraphs. Applying this to $\\overline{G}$ (where $\\chi$ and $\\alpha$ swap roles with $\\omega$ a...

From: Introduction to Graph Theory

Learn more: https://west-graphs-deploy.vercel.app/#/section/23

Explore all courses: https://mathacademy-cyan.vercel.app