This question already has an answer here:
- Partition into interval graphs 1 answer
I am re-opening this question as i have the following question. I was going through the paper by Farrugia which was mentioned in an answer in that post. Initially i beleived that the follwoing problem is NP-Complete.
Suppose there is a graph $G=(V,E)$. I want to test if V can be partitioned into two disjoint sets $V_1$ and $V_2$ such that the subgraphs induced by $V_1$ and $V_2$ are unit interval graphs.
But in the paper,there is a theorem which says
Let $A$ and $B$ be additive induced-hereditary properties. Then there is a polynomial-time transformation from the $A$-recognition problem to the $(A◦B)$-recognition problem.
So, my question is that :- is it possible that because of the above theorem the problem might be solvable in polynomial time ??