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.

  • 2
    $\begingroup$ Assuming $|V(G)|=n$, I believe you mean $\chi(G)+\chi(G')\geq n+1$ $\endgroup$ – 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.