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

2 Answers 2

3

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.

  • 0
    How does that lead to the conclusion that $\chi(G)\cdot\chi(\overline{G})\geq |V|$ ?2012-02-07
  • 0
    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.2012-02-08
0

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

  • 0
    Welcome to MSE! Are those supposed to be overlines? Regards2013-05-18