3
$\begingroup$

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.
$\endgroup$

1 Answer 1

5
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.