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