How to demonstrate that $\chi(\bar G)=\omega(\bar G)$ , $G$ is a bipartite graph

Question

If G is a bipartite graph then $\chi(\bar G)=\omega(\bar G)$?

Answer 1

Suppose we have a partition of the complement of $G$ into two cliques $X$ and $Y$ where $|X|=n$ is maximal. We prove the result by induction on $|Y|$. Assume $X$ is colored with $c_1,c_2,\ldots,c_n$ distinct colors. If $Y$ is empty, then we are done. Otherwise assume we have colored $X\cup(Y-\{y\})$ properly. We want to choose a color for $y$. If $y$ is not adjacent to some unused color, then choose that color. Assume therefore that $y$ is adjacent to all unused colors. If every other vertex in $Y$ were adjacent to all of these $|X|-|Y|+1$ colors as well, then we would have a clique of size $|X|+1$, contradicting maximality. Thus let $y'$ be a vertex with color $c$ and let $c'$ be an unused color that $y'$ is not adjacent to. Let $c''$ be a color in $X$ that $y$ is not adjacent to and let $y''$ be the vertex in $Y$ with color $c''$. Then color $y'$ with $c'$, $y''$ with $c$, and $y$ with $c''$. This is a proper coloring, and the result follows by induction.