Showing that $n \leq \chi(G)\chi(G')$ and $\chi(G') + \chi(G) \geq 2\sqrt n$.

Question

Let $n$ be the number of vertices of $G$. Recall that $G'$ denotes the complement of $G$. Show that
a) $n \leq \chi(G)\chi(G')$ and therefore,
b) $\chi(G') + \chi(G) \geq 2\sqrt n$.

This question was on my graph theory exam and I didn't know how to approach solving it.

Any tips on how to approach this would be greatly appreciated!

Answer 1

So Given a coloring c and c' of G and G' using $\chi(G)$ and $\chi(G')$ colors, we get a coloring for the complete graph $G\cup G'$ by associating a vertex u the color $(c(u),c'(u))$. And so $n \leq \chi(G)\chi'(G)$.

Now, $(\chi(G)-\chi'(G))^2 \geq 0$ so $\chi(G)^2-2\chi(G)\chi'(G)+\chi'(G)^2\geq0$ so $\chi(G)^2+2\chi(G)\chi'(G)+\chi'(G)\geq 4\chi(G)\chi'(G)$ so $(\chi(G)+\chi'(G))^2\geq 4n$ so $\chi(G)+\chi'(G) \geq 2\sqrt{n}$ !