Proving that $\chi(G)=\omega(G)$ if the complement of G is bipartite.

Question

***Please note I am aware that this question was already asked here: Proving that $ \chi(G) = \omega(G) $ if $ \bar{G} $ is bipartite. however, I have a reason to believe the answer given in that topic is flawed.

What I so far tried: I divided the complement of G to parts V and U, while all isolated vertices belong to V and |V| is bigger than |U|. $|V|≤\omega(G)$ so I gave the vertices of V distinct colors (they are a clique in G), now all that is left to show is that the vertices of U can be colored in G without adding extra colors. the answer in the linked topic suggests that since every vertex of U has a neighbor in V in the complement of G, you can give each vertex in U the color of one of its neighbors. that is not really the case, since two vertices of U can potentially only be adjacent to the same vertex in V, and since U is a clique in G, you cannot give them the same color. this method can only work if one can prove that the complement of G has a matching that spawns all vertices of U. this is not the case for certain graphs, and so this method fails.

edit: here is a complement graph for which |V| is smaller than $\omega(G)$. (top two blue vertices and lower four red vertices form a 6 clique in G.)

Answer 1

Lemma 1: Let $S'$ be a largest independent set in a bipartite graph $H$ and let us set $T' \doteq V(H) \setminus S'$. Then $|N_H(Y) \cap S'| \geq |Y|$ for every subset $Y$ of $T'$.

Proof: Write the parts of $H$ as $S$ and $T$ [note that $S'$ may be neither $S$ nor $T$]. Suppose that there is a subset $U$ of $S \setminus S'$ s.t. $|(N_H(U) \cap S')| < |U|$. Then note that $U$ is independent. So $S'' = (S' \setminus (N_H(U) \cap S')) \cup U$ is also independent and is strictly larger than $S'$. So there cannot be such a subset $U$ of $S$. Likewise there cannot be such a subset $X$ of $T \setminus S'$.

Now let $Y$ be a subset of $(S \setminus S') \cup (T \setminus S')$ or equivalently let $Y$ be a subset of $V(H) \setminus S'$. Write $U \doteq Y \cap S$ and $X \doteq Y \cap T$. Then $|N_H(Y) \cap S'| = |N_H(U) \cap S'| + |N_H(X) \cap S'|$ [because $H$ is bipartite $N_H(U)$ and $N_H(X)$ do not intersect] while $|Y| = |U| + |X|$. So $|N_H(Y \cap S' )| = |N_H(U) \cap S'| + |N_H(X) \cap S'|$ $\geq |U|+|X| \geq |Y|$ [from the above paragraph]. Thus Lemma 1 follows. $\surd$

We now use Lemma 1 to finsh the proof of the exercise. Let $S'$ be the largest independent set in $G^c\doteq H$. Then $S'$ is a clique in $G$, so to finish the proof it suffices to give a proper coloring of $G$ with only $|S'|$ colors. We do this next.

We first note the following: Then as $H$ is bipartite by Lemma 1 and Hall's MAtching Theorem there is a matching $M^c$ in $H$ such that (a) every edge in $M^c$ has one edge in $S'$ and the other in $T' \doteq V(H)\setminus S'$, and (b) every vertex in $T'$ is covered.

We now give the coloring of $G$: Give every vertex in $S'$ a color from 1 through $|S'|$ and for each vertex $v \in T'$ give $v$ the color of the vertex that $v$ is matched with in $M^c$. The above coloring is a proper coloring in $G$.

Answer 2

Using the notation $G^c$ for complement, and $\alpha(G)$ for the stability number of $G$

The proposed proof went just a bit fast on the definition of $U$ and $V$. With its definition, you could have that $V$ is not the biggest independent set in $G^c$.

The key point is that you need $\vert V \vert \geq \vert U \vert$ before taking into account the isolated vertices of $G^c$, so that $\vert V\vert = \omega(G)=\alpha(G^c)$

Then if two elements of $U$, $u_1$ and $u_2$ are connected to the same vertices $v$ of $V$, then at least one of them must be connected to another vertices $v' \in V$.

The detailled written proof is a bit tedious, but try drawing appropriate graph, it's much easier to see. If need be I'll put the proof here tonight.