<p>I think, your problem is NP-complete. It is a special case of <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r46/pdf">a theorem 
by Farrugia</a>, 
stating that it is NP-hard to test if the vertex set a graph can be partitioned into 
two subsets $V_1,$ and $V_2$ such that $G(V_1)$ belongs to the graph class $\mathcal{P}$ and 
$G(V_2)$ belongs to the graph class $\mathcal{Q}$, provided $\mathcal{P}$ and $\mathcal{Q}$ 
are closed under taking vertex-disjoint unions and talking induced subgraphs, and at least 
one of $\mathcal{P}$ and $\mathcal{Q}$ is non-trivial (meaning not all graphs in the class are 
edgeless). </p>

CC BY-SA 3.0
2014-02-04T20:52:24.180Z
2014-02-04T20:52:24.180Z
vb le
<p>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.</p>

<p>I know about the NP-completeness of determining interval numbers but the above problem is different.
Now, in the literature I found <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4915" rel="nofollow">this</a> work by A. Gyárfás and D. West on multitrack interval graphs but I'm not sure if it is relevant to above problem.</p>

<p>Any citation to existing literature on the above or similar problem would be helpful. Also please let me know if there is a formal name for the above problem.</p>

CC BY-SA 3.0
2014-02-04T19:36:10.373Z
Isn't the recognition of a 2-track graph (in the West paper) exactly your problem ?
Suresh Venkat
CC BY-SA 3.0
2014-02-04T20:45:59.790Z
I think recognizing 2-track graphs is the edge-version of the problem.
vb le
<graph-theory><partition-problem><interval-graphs>
Partition into interval graphs
Dibyayan
# Partition into interval graphs

(Asked by: username_0 on 2014-02-02)

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.

I know about the NP-completeness of determining interval numbers but the above problem is different.
Now, in the literature I found [this](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.4915) work by A. Gyárfás and D. West on multitrack interval graphs but I'm not sure if it is relevant to above problem.

Any citation to existing literature on the above or similar problem would be helpful. Also please let me know if there is a formal name for the above problem.

**Tags:** graph-theory, partition-problem, interval-graphs
> **Comments:**
> **username_1**: Isn't the recognition of a 2-track graph (in the West paper) exactly your problem ?  
> **username_2**: I think recognizing 2-track graphs is the edge-version of the problem.  

---

## 1 answers

### Answer by username_2 on 2014-02-04. Score: 21 | Accepted answer

I think, your problem is NP-complete. It is a special case of [a theorem
by Farrugia](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r46/pdf),
stating that it is NP-hard to test if the vertex set a graph can be partitioned into
two subsets $V\_1,$ and $V\_2$ such that $G(V\_1)$ belongs to the graph class $\mathcal{P}$ and
$G(V\_2)$ belongs to the graph class $\mathcal{Q}$, provided $\mathcal{P}$ and $\mathcal{Q}$
are closed under taking vertex-disjoint unions and talking induced subgraphs, and at least
one of $\mathcal{P}$ and $\mathcal{Q}$ is non-trivial (meaning not all graphs in the class are
edgeless).


---

