World's most popular travel blog for travel bloggers.

[Answers] Relationship between Coloring a graph and its complement

, , No Comments
Problem Detail: 

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)

Asked By : Vitor

Answered By : tarulen

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.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback