# Chromatic number in relation to the amount of vertices

We have a finite undirected graph $G := (V, E)$ and its complementary graph $\overline G := (\overline V, \overline E)$. How do we show that $\chi (G) \cdot \chi (\overline G) \ge |V|$?

We know that there is a subset $V'$ in $V$ with $|V'| \ge \frac{|V|}{\chi (G)}$ and it also applys to $\overline G$. I started with transforming the given inequality to $\chi(G)$, respectivly $\chi(\overline G)$, so that $$\chi(G) \ge \frac{|V|}{|V'|} ,$$ and $$\chi(\overline G) \ge \frac{|V|}{|\overline V'|} .$$ And put both together: $$\chi(G) \cdot \chi(\overline G) \ge \frac{|V|^2}{|V|\cdot|\overline V'|} .$$ But how do I eleminate the $|V|\cdot|\overline V'|$, or show that $$\frac{|V|^2}{|V|\cdot |\overline V'|} \ge |V|?$$

-

Color $G$ with a coloring $f$ and color $\bar{G}$ with a coloring $g$, now color all the vertices with ordered pairs $(f,g)$, and check that every vertex gets a different ordered pair.
How does that lead to the conclusion that $\chi(G)\cdot\chi(\overline{G})\geq |V|$ ? – Robert S. Barnes Feb 7 '12 at 9:50
I see now. The one to one function shows that any in any coloring of the two graphs, including a minimal coloring, there must be at least $|V|$ colors in the Cartesian product of the color sets. – Robert S. Barnes Feb 8 '12 at 6:52
$$\chi(G)\chi(\overline{G})\ge\chi(G)w(\overline{G})\ge\chi(G)\alpha(G)\ge V(G)$$ where $w(\overline{G})$ is a maximal complete subgraph of $\overline{G}$, and $\alpha(G)$ is a maximal stable subset of $G$.