Prove $\chi(G)\chi(\bar{G}) \geq n$ for chromatic number of graph and its complement

Question

Let us denote by $\chi(G)$ the chromatic number, which is the smallest number of colours needed to colour the graph $G$ with $n$ vertices. Let $\bar{G}$ be the complement of $G$. Show that

(a) $\chi(G)+\chi(\bar{G}) \leq n+1$

(b) $\chi(G)\chi(\bar{G}) \geq n$

I was able to prove (a) using induction. Any hints on proving (b)?

Answer 1

Hint: consider the graph with:

• vertex set $G \times G$

• edges between $(v, w)$ and $(x, y)$ iff there is an edge $v$ to $x$ in $G$ or there is an edge $w$ to $y$ in $\bar{G}$

• colouring $C(v, w) = (c(v), \bar{c}(w))$ where $c$ is the colouring of $G$ and $\bar{c}$ is the colouring of $\bar{G}$.

If you're wondering where I got this from, I just tried to find a graph that had the information of $G$ in it and was coloured by $\chi(G)\chi(\bar{G})$ colours.

Answer 2

I upped user73985's proof as it's a nice constructive way to do it.
Here's an alternative.

Say that $\chi(G) = k$. Then $V(G)$ can be partitioned into $k$ sets, each consisting of vertices that share no edge. There must be one of these sets $X$ that has at least $n/k$ vertices. But $X$ forms a complete graph in $\overline{G}$, so $\chi(\overline{G}) \geq n/k$.

And thus $\chi(G)\chi(\overline{G}) \geq k \cdot n/k = n$.

Answer 3

Suppose the chromatic number of $G$ is $k$ and that $V_1,\ldots,V_k$ are the color classes. Each $V_i$ is an independent set of $G$ and hence a clique in the complement of $G$. The chromatic number of $\overline{G}$ is at least its clique number, and so $\chi(\overline{G}) \ge |V_i|$ for all $i$. In particular, $\chi(\overline{G})$ is at least the size of the largest color class. The largest color class has size at least the average size $n/k$ of a color class. Thus, $\chi(\overline{G}) \ge \lceil n/k \rceil$. Hence $\chi(G) \chi(\overline{G}) \ge k \cdot \lceil n/k \rceil \ge n$

Answer 4

$(b)$ Prove that $\chi(G)\cdot \chi(G')\geq n$.

Proof: For every graph $G$ and $G'$ we know that $\chi(G)\geq {n\over \alpha(G)}$ and $\chi(G')\geq \omega(G')=\alpha(G)$ where $\alpha(G)$ and $\omega(G)$ denote the independence number and clique number of $G$. So $\chi(G)\cdot \chi(G')\geq {n\over \alpha(G)}\cdot \alpha(G)=n$. Thus $\chi(G)\cdot \chi(G')\geq n$.