Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

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$

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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