Prove $\chi(G)\chi(\bar{G}) \geq n$ for chromatic number of graph and its complement Let us denote by $\chi(G)$ the chromatic number, which is the smallest number of colours needed to colour the graph $G$ with $n$ vertices. Let $\bar{G}$ be the complement of $G$. Show that
(a) $\chi(G)+\chi(\bar{G}) \leq n+1$
(b) $\chi(G)\chi(\bar{G}) \geq n$
I was able to prove (a) using induction. Any hints on proving (b)?
 A: Hint: consider the graph with:


*

*vertex set $G \times G$

*edges between $(v, w)$ and $(x, y)$ iff there is an edge $v$ to $x$ in $G$ or there is an edge $w$ to $y$ in $\bar{G}$

*colouring $C(v, w) = (c(v), \bar{c}(w))$ where $c$ is the colouring of $G$ and $\bar{c}$ is the colouring of $\bar{G}$.
If you're wondering where I got this from, I just tried to find a graph that had the information of $G$ in it and was coloured by $\chi(G)\chi(\bar{G})$ colours.
A: I upped user73985's proof as it's a nice constructive way to do it.
Here's an alternative.  
Say that $\chi(G) = k$.  Then $V(G)$ can be partitioned into $k$ sets, each consisting of vertices that share no edge.  There must be one of these sets $X$ that has at least $n/k$ vertices.  But $X$ forms a complete graph in $\overline{G}$, so $\chi(\overline{G}) \geq n/k$.
And thus $\chi(G)\chi(\overline{G}) \geq k \cdot n/k = n$.
A: $(b)$ Prove that $\chi(G)\cdot \chi(G')\geq n$.
Proof: For every graph $G$ and $G'$ we know that $\chi(G)\geq {n\over \alpha(G)}$ and $\chi(G')\geq \omega(G')=\alpha(G)$ where $\alpha(G)$ and $\omega(G)$ denote the independence number and clique number of $G$. So $\chi(G)\cdot \chi(G')\geq {n\over \alpha(G)}\cdot \alpha(G)=n$. Thus $\chi(G)\cdot \chi(G')\geq n$.
A: Suppose the chromatic number of $G$ is $k$ and that $V_1,\ldots,V_k$ are the color classes.  Each $V_i$ is an independent set of $G$ and hence a clique in the complement of $G$.  The chromatic number of $\overline{G}$ is at least its clique number, and so $\chi(\overline{G}) \ge |V_i|$ for all $i$.  In particular, $\chi(\overline{G})$ is at least the size of the largest color class. The largest color class has size at least the average size $n/k$ of a color class.  Thus, $\chi(\overline{G}) \ge \lceil n/k \rceil$.  Hence $\chi(G) \chi(\overline{G}) \ge k \cdot \lceil n/k \rceil \ge n$ 
