Prove that G is perfect

94 Views Asked by At

Prove that $\chi(G) = \omega(G)$ when $\bar G$ is bipartite.

($\chi(G)$ is the chromatic number in G, $\omega(G)$ is the maximum size of a clique in G)

Proof: If $\bar G$ is bipartite then $\chi(\bar G) = \omega(\bar G)$ just because bipartite graphs are $2$-colorable and the maximum size of a clique in a bipartite graph is $2$, so $\bar G$ is perfect. Now note that the complement of $\bar G = G$ and by the $weak$ perfect graph theorem, a graph is perfect if and only if its complement is perfect, therefore $G$ is also perfect, i.e. $\chi(G) = \omega(G)$. Does this prove the statement?