Partition en graphiques d'intervalle

Supposons qu'il existe un graphique . Je veux tester si peut être partitionné en deux ensembles disjoints et telle sorte que les sous-graphes induits par et sont des graphiques d'intervalle d'unité.$G=(V,E)$$V$$V_1$$V_2$$V_1$$V_2$

Je connais la complétude NP de la détermination des nombres d'intervalles mais le problème ci-dessus est différent. Maintenant, dans la littérature, j'ai trouvé ce travail de A. Gyárfás et D. West sur des graphiques d'intervalles multipistes, mais je ne sais pas s'il est pertinent pour le problème ci-dessus.

Toute citation à la littérature existante sur le problème ci-dessus ou similaire serait utile. Veuillez également me faire savoir s'il existe un nom officiel pour le problème ci-dessus.

Je pense que votre problème est NP-complet. C'est un cas particulier d' un théorème de Farrugia , déclarant qu'il est difficile de vérifier si le sommet défini par un graphe peut être partitionné en deux sous-ensembles et V 2 tels que G ( V 1 ) appartient à la classe de graphe P et G ( V 2 ) appartiennent à la classe de graphes Q , à condition que P et$V_1,$$V_2$$G(V_1)$$\mathcal{P}$$G(V_2)$$\mathcal{Q}$$\mathcal{P}$$\mathcal{Q}$$\mathcal{P}$$\mathcal{Q}$ n'est pas trivial (ce qui signifie que tous les graphiques de la classe sont sans bord).