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

Question

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.

Answer 1

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$

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