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

Is there any relation between the chromatic number of a graph $G$ and its complement $G'$ that are always true?

I saw these ones: $\chi(G)\chi(G')\geq n$ and $\chi(G)+\chi(G')\geq 2n$,

but I'm not pretty sure about them.

• Assuming $|V(G)|=n$, I believe you mean $\chi(G)+\chi(G')\geq n+1$ – Holdsworth88 Jun 15 '12 at 13:07

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

You're actually not quite right. so your inplication that every vertex of H has degree less than or equal to q - 1 is not true. as long as one of these has degree less than or equal to q - 1, the complement graph's degree would be equal to n - q.

$(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}$.