Aufteilung in Intervallgraphen

Angenommen, es gibt einen Graphen . Ich möchte testen, ob V in zwei disjunkte Mengen V 1 und V 2 unterteilt werden kann, so dass die durch V 1 und V 2 induzierten Teilgraphen Einheitsintervallgraphen sind.$G=(V,E)$$V$$V_1$$V_2$$V_1$$V_2$

Ich weiß um die NP-Vollständigkeit bei der Bestimmung von Intervallnummern, aber das obige Problem ist anders. In der Literatur habe ich diese Arbeit von A. Gyárfás und D. West zu mehrspurigen Intervallgraphen gefunden, aber ich bin mir nicht sicher, ob sie für das obige Problem relevant ist.

Jede Angabe zu vorhandener Literatur zu dem oben genannten oder einem ähnlichen Problem wäre hilfreich. Bitte lassen Sie mich auch wissen, ob es einen offiziellen Namen für das oben genannte Problem gibt.

Ich denke, dein Problem ist NP-vollständig. Es ist ein Spezialfall eines Satzes von Farrugia , die besagen , dass es NP-schwer zu testen ist , wenn der Scheitelpunkt ein Graph festlegen kann in zwei Untermengen unterteilt werden , und V 2 , so dass G ( V 1 ) gehört zur Graph Klasse P und G ( V 2 ) gehören zur Graphenklasse Q , vorausgesetzt, dass P und Q unter Verwendung von vertex-disjunkten Vereinigungen und sprechenden induzierten Teilgraphen und mindestens einem von P und $V_1,$$V_2$$G(V_1)$$\mathcal{P}$$G(V_2)$$\mathcal{Q}$$\mathcal{P}$$\mathcal{Q}$$\mathcal{P}$$\mathcal{Q}$ ist nicht trivial (was bedeutet, dass nicht alle Grafiken in der Klasse kantenlos sind).