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$ – Jsevillamol Sep 13 '16 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$ – Hilder Vitor Lima Pereira Sep 13 '16 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$ – David Richerby Sep 13 '16 at 13:25

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 Sep 13 '16 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$ – David Richerby Sep 13 '16 at 13:21
  • 1
    $\begingroup$ Well, at least I didn't prove a false statement (: $\endgroup$ – Hilder Vitor Lima Pereira Sep 13 '16 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 Sep 13 '16 at 15:13

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.