the Nordhaus-Gaddum problems for chromatic number of graph and its complement

The following proof is taken from Graphs and Digraphs by Chartrand, Lesniak, and Zhang, who attribute proof to Hudson V. Kronk.

Let $G$ be a graph such that $V(G)=n$. Suppose $\chi(G)=k$ and $\chi(\overline{G})=l$. Assume we are given a $k$-coloring $c$ and $l$-coloring $\overline{c}$ of $G$ and $\overline{G}$, respectively. With these colorings, one can obtain a coloring of $K_n$. To each vertex $v$ of $G$ (and also $\overline{G}$) one associates the ordered pair $\{c(v),\overline{c}(v)\}$. Given distinct vertices $v$ and $w$ in $K_n$, one notes that $v$ and $w$ must be adjacent in either $G$ or $\overline{G}$, so this gives a coloring of $K_n$ using at most $kl$ colors. Therefore,

$$\chi(K_n)=n\leq kl=\chi(G)\cdot \chi(\overline{G}).$$

To prove $\chi(G)+\chi(\overline{G})\leq n+1$ we use the following lemma:

Lemma: For every graph $G$

$$\chi(G)\leq 1+\operatorname{max}\{\delta(H)\},$$

where $H$ is a subgraph of $G$ and the maximum is taken over all the subgraphs $H$ of $G$.

Let $q=\operatorname{max}\{\delta(H)\}$. Then, by the above lemma, we have $\chi(G)\leq 1+q$. Next we determine $\operatorname{max}\{\delta(\overline{G})\}$, which I claim is $n-q-1$. Assume the contrary. Then there is a subgraph $H$ of $G$ such that $\delta(\overline{H})\geq n-q$. This implies every vertex of $H$ has degree less than or equal to $q-1$. Let $K$ be a subgraph of $G$ such that $\delta(K)=q$ (note such a subgraph exists since $q=\operatorname{max}\{\delta(H)\}$). Clearly no vertex in $K$ is in $H$. Now, $|V(K)|\geq q+1$ since $\delta(K)=q$, which implies

$$|V(H)|\leq n-(q-1)=n-q-1,$$

contradicting the fact $\delta(\overline{H})\geq n-q$. Therefore $\operatorname{max}\{\delta(\overline{G})\}\leq n-q-1$, which implies by the lemma that $\chi(\overline{G})\leq 1+(n-q-1)=n-q$. Putting this all together gives

$$\chi(G)+\chi(\overline{G})\leq (1+q)+(n-q)=n+1.$$

More relations between the chromatic number of a graph and its complement are:

• $2\sqrt{n}\leq \chi(G)+\chi(\overline{G})$

• $\chi(G)\cdot \chi(\overline{G})\leq (\frac{n+1}{2})^2$

$(a)$ 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$.

$(b)$ Prove that $\chi(G)+\chi(G')\geq 2\sqrt{n}$.

Proof: Since both $\chi(G)$ and $\chi(G')$ are at least one we know that $(\chi(G)-\chi(G'))^2\geq 0$ and so $\chi(G)^2-2\chi(G)\cdot \chi(G')+\chi(G')^2\geq 0$. Adding $4\chi(G)\cdot \chi(G')$ to both sides of the equation we obtain $\chi(G)^2+2\chi(G)\cdot\chi(G')+\chi(G')^2\geq 4\chi(G)\cdot\chi(G')$ and factoring the left-hand side we now have $(\chi(G)+\chi(G'))^2\geq 4\chi(G)\cdot\chi(G')$. Taking the square root of both sides gives us $\chi(G)+\chi(G')\geq 2\sqrt{\chi(G)\cdot \chi(G')}$ and since $\chi(G)\cdot \chi(G')\geq n$ by the previous result in $(a)$ we can conclude that $\chi(G)+\chi(G')\geq 2\sqrt{n}$.