Proving that $ \chi(G) = \omega(G) $ if $ \bar{G} $ is bipartite.

Question

I know that $ \chi \! \left( \bar{G} \right) = 2 $ and that $ \chi(G) \geq \alpha \! \left( \bar{G} \right) $, but how can I conclude that $ \chi(G) = \omega(G) $?

Answer 1

First, it’s always true that $\chi(G)\ge\omega(G)$, so your real problem is to show that $\chi(G)\le\omega(G)$ if $\overline{G}$ is bipartite. Note that it need not be true that $\chi(\overline{G})=2$: the chromatic number of a bipartite graph is $1$ if the graph has no edges. In that case $G$ is a complete graph, and the result is trivial, so I’ll assume that $G$ is not complete.

Suppose that $\overline{G}$ is bipartite with parts $V$ and $W$. Without loss of generality we may assume that all isolated vertices of $\overline{G}$ belong to $V$, and that $|V|\ge|W|$. Clearly $V$ is a clique in $G$. Color each vertex of $V$ with a different color. Now observe that for each $w\in W$ there is at least one $v\in V$ such that $vw$ is an edge of $\overline{G}$ and hence such that $wv$ is not an edge of $G$, so that $w$ can be given the same color as $v$. Thus, $\chi(G)\le|V|\le\omega(G)$.

Added 22 November 2021:

The final step in the argument is incorrect: it is not necessarily true that $w$ can be given the same color as $v$. There might be a vertex $w'\in W\setminus\{w\}$ such that $v$ is the only vertex of $V$ adjacent to either $w$ or $w'$ in $\overline{G}$. Then the argument would make both $w$ and $w'$ the same color as $v$, but in fact $w$ and $w'$ are adjacent in $G$ and therefore cannot be given the same color. This error was noted in this question, and the accepted answer to that question also solves this one.