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 likeIf $G$ accepts a $k$-coloring, than $G^*$ accepts a $(n - k)$-coloringbut I can't prove that.(Of course, I am dealing with proper coloring)
Relationship between Coloring a graph and its complement
graph theory;colorings
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.