patternMinor
Given the optimal coloring of a graph how will we find the optimal coloring of its complement graph?
Viewed 0 times
findthecoloringoptimalgraphitswillhowcomplementgiven
Problem
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:
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:
- An algorithm that computes $\chi(\overline{G})$
- A proof that $\chi(\overline{G})$ cannot be found in polynomial time from $\chi(G)$.
- If 2 is true then is there any existing approximation and randomized solutions.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#151069, answer score: 5
Revisions (0)
No revisions yet.