Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|?$$

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer
Welcome to MSE! Are those supposed to be overlines? Regards – Amzoti May 18 '13 at 22:11

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.