Partisi ke dalam grafik interval

Misalkan ada grafik . Saya ingin menguji apakah V dapat dipartisi menjadi dua set disjoint V 1 dan V 2 sehingga subgraph yang diinduksi oleh V 1 dan V 2 adalah grafik satuan interval.$G=(V,E)$$V$$V_1$$V_2$$V_1$$V_2$

Saya tahu tentang NP-kelengkapan penentuan angka interval tetapi masalah di atas berbeda. Sekarang, dalam literatur saya menemukan karya ini oleh A. Gyárfás dan D. West pada grafik interval multitrack tapi saya tidak yakin apakah itu relevan dengan masalah di atas.

Setiap kutipan untuk literatur yang ada tentang masalah di atas atau yang serupa akan sangat membantu. Tolong juga beri tahu saya jika ada nama resmi untuk masalah di atas.

Saya pikir, masalah Anda sudah selesai NP. Ini adalah kasus khusus dari teorema oleh Farrugia , yang menyatakan bahwa NP-sulit untuk menguji apakah vertex set grafik dapat dipartisi menjadi dua himpunan bagian dan V 2 sehingga G ( V 1 ) termasuk dalam kelas grafik P dan G ( V 2 ) termasuk dalam kelas grafik Q , asalkan P dan Q ditutup dengan mengambil serikat pisah-pisah-simpul dan berbicara dengan subgraf yang diinduksi, dan setidaknya satu dari P dan $V_1,$$V_2$$G(V_1)$$\mathcal{P}$$G(V_2)$$\mathcal{Q}$$\mathcal{P}$$\mathcal{Q}$$\mathcal{P}$$\mathcal{Q}$ bersifat non-trivial (artinya tidak semua grafik di kelas edgeless).