Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

2 Answers 2

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|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|improve this answer
    
Welcome to MSE! Are those supposed to be overlines? Regards –  Amzoti May 18 '13 at 22:11

Your Answer

 
discard

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.