9
$\begingroup$

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
    Assuming $|V(G)|=n$, I believe you mean $\chi(G)+\chi(G')\geq n+1$2012-06-15

3 Answers 3