# Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?

Suppose the optimal color assignment of graph $$G$$ is given. Does there exist any polynomial-time algorithm that provides the optimal color assignment of its complement graph $$\overline{G}$$?

A relation between $$\chi(G)$$ and $$\chi(\overline{G})$$ is present here. But it is not providing the exact value of $$\chi(\overline{G})$$ in the general case. So my belief is that the answer to the question above is No or Unknown. I am looking for either of the following:

1. An algorithm that computes $$\chi(\overline{G})$$
2. A proof that $$\chi(\overline{G})$$ cannot be found in polynomial time from $$\chi(G)$$.
3. If 2 is true then is there any existing approximation and randomized solutions.

Morandini, NP-complete problem: partition into triangles shows that the following problem is NP-complete: Given a tripartite graph $$G$$ on $$3n$$ vertices (given together with a tripartition), determine whether $$G$$ contains $$n$$ vertex-disjoint triangles.
Since the graph $$G$$ is tripartite, we can construct an optimal coloring of $$G$$. First, we check whether $$G$$ is bipartite, and if so, we construct an optimal 2-coloring of $$G$$ (or a 1-coloring, if $$G$$ is empty). Otherwise, we use the given tripartition to construct an optimal 3-coloring of $$G$$.
We claim that $$\chi(\overline{G}) = n$$ iff $$G$$ contains $$n$$ vertex-disjoint triangles. Since each triangle in $$G$$ corresponds to an independent set in $$\overline{G}$$, if $$G$$ contains $$n$$ vertex-disjoint triangles (which necessarily cover all vertices of $$G$$), then we can color $$\overline{G}$$ using $$n$$ colors by coloring the $$i$$'th triangle with color $$i$$. Conversely, suppose that $$\chi(\overline{G}) = n$$. Since $$G$$ is tripartite, each color class of $$\overline{G}$$ contains at most 3 vertices (otherwise it would contain at least two vertices in the same part, which are connected by an edge in $$\overline{G}$$). Since $$\overline{G}$$ has exactly $$3n$$ vertices, each color class must consist of precisely 3 vertices, which form a triangle in $$G$$.