Let $G = (V, E)$ be a graph and $G^*$ its edge complement (that is, $G^* = (V, E^*)$, where an edge $\{u, v\} \in E^* \Leftrightarrow \{u, v\} \not \in E$).

What is the relationship between a coloring in $G$ and a coloring in $G^*$ ?

I was expecting something like

"If $G$ accepts a $k$-coloring, than $G^*$ accepts a $(n - k)$-coloring"

but I can't prove that.

(Of course, I am dealing with proper coloring)

  • 2
    $\begingroup$ The claim is false. Take a complete graph of $5$ nodes and remove any edge, and call that $G$. Then $G$ is $4$-colorable, but certainly $G^*$ is not 1-colorable. $\endgroup$ Commented Sep 13, 2016 at 11:46
  • $\begingroup$ Thanks! What about the chromatic numbers? For the complete graph $K_5$, it is $5$, and for its complement, it is $1$. Maybe there is some relation of the type $X(G) = k \Leftrightarrow X(G^*) = n - k + 1$... What do you think? $\endgroup$ Commented Sep 13, 2016 at 13:20
  • 1
    $\begingroup$ @Vitor Take the 4-cycle, which has chromatic number 2. Its complement is a pair of disjoint edges, which has chromatic number $2\neq 4-2+1$. $\endgroup$ Commented Sep 13, 2016 at 13:25

1 Answer 1


Sorry, this is false:

For example, take $G$ as a size-$10$ independent set. It has a $1$-coloring, or even a $3$-coloring... its complement is a clique, which admits neither a $9$- nor $7$-coloring.

  • $\begingroup$ However, I think you might get something like $n-k-2$ where $k$ is the smallest integer such that $G$ is $k$-colorable... I don't have a proof though $\endgroup$
    – tarulen
    Commented Sep 13, 2016 at 11:49
  • $\begingroup$ The 5-cycle has chromatic number 3. Its complement is still a 5-cycle, which does not have a proper colouring with 5-3-2=0 colours. $\endgroup$ Commented Sep 13, 2016 at 13:21
  • 1
    $\begingroup$ Well, at least I didn't prove a false statement (: $\endgroup$ Commented Sep 13, 2016 at 13:21
  • $\begingroup$ Right, my conjecture was $n-k+2$, I misstyped there. I don't find a counter-example but I didn't try too much though. $\endgroup$
    – tarulen
    Commented Sep 13, 2016 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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