Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Is it true that for perfect graphs the following holds:
A maximum size of an independent set in a graph $G$ equals to the chromatic number of $\overline{G}$, where $\overline{G}$ is the complement of $G$ of course.
If yes, what would be the reference?
By the perfect graph theorem (conjectured by Claude Berge in 1961 and proved by László Lovász in 1972 [L]), a graph is perfect iff its complement is perfect. Therefore a chromatic number of $\overline{G}$ equals to its clique number, which equals to an independence number of $G$.
References
[L] L. Lovász, A characterization of perfect graphs, J. combin. theory ser. B 13 (1972) 95–98.
