# Relationship between Coloring a graph and its complement

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)

• 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. – Jsevillamol Sep 13 '16 at 11:46
• 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? – Hilder Vitor Lima Pereira Sep 13 '16 at 13:20
• @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$. – David Richerby Sep 13 '16 at 13:25

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.
• 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 – tarulen Sep 13 '16 at 11:49
• 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. – tarulen Sep 13 '16 at 15:13