2
$\begingroup$

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

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How does that lead to the conclusion that $\chi(G)\cdot\chi(\overline{G})\geq |V|$ ? $\endgroup$ Feb 7, 2012 at 9:50
  • $\begingroup$ 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. $\endgroup$ Feb 8, 2012 at 6:52
0
$\begingroup$

$$ \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$.

$\endgroup$
1
  • $\begingroup$ Welcome to MSE! Are those supposed to be overlines? Regards $\endgroup$
    – Amzoti
    May 18, 2013 at 22:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .