As in the title, for every graph $G$, we want to find a bipartition $V(G)=S\cup T$ such that $$\chi(G[S])+\chi(G[T])=\chi(G). $$
My attempt is to find a set $S\subseteq V(G)$ of vertices such that each vertex of $S$ is adjacent to all the vertices in $T=V(G)\setminus S$. This will naturally give the equality we want.
But the main problem is how we can find out such subset $S$. Is there any good algorithm for this? Or am I approaching this problem in a wrong way? Any help will be appreciated.
I'll show how to compute $\chi(G)$ for a general graph using this algorithm.
Given a graph $G$ we w
If there were a polynomial algorithm, with
Then one could use it to find $\chi(G)$ of any graph.
Polynomial reduction from exact-coloring problem to the stated problem:
Given a graph $G=(V,E)$, we can use the algorithm recursively to find what is $\chi(G)$.
The complexity of this algorithm is: $$T(n)=T(k)+T(n-k) + poly(n)$$ where $1\leq k\leq n$.
By assuming $T(1)=O(1)$ we get: $$ T(n)=poly(n)$$
Think on the recursion $T(n)=T(k)+T(n-k) + poly(n)$ as a binary tree, where every non-leaf vertex has two children. We pay at most $poly(n)$ on every such non-leaf vertex. The question is then reduced to what is the maximal number of vertices in a tree with $n$ leaves where every non-leaf vertex has two children.
one can show by induction the answer is $2n-1$. Therefore, the overall running time is $poly(n)$.
Since this is an $\text{NP-Complete}$ problem (link), we do not know if such an algorithm exists, although it is widely assumed there is no polynomial algorithm to solve this problem.
As for an actual answer to your question, a brute force approach - in which you go through all of the options, will turn out to be not "so bad", compared to others, in the general case.