Podział na wykresy interwałowe

Załóżmy, że istnieje wykres . Chcę sprawdzić, czy można podzielić na dwa rozłączne zestawy i tak, że podgrupy indukowane przez i są wykresami interwałów jednostkowych.$G=(V,E)$$V$$V_1$$V_2$$V_1$$V_2$

Wiem o kompletności NP określania liczb przedziałów, ale powyższy problem jest inny. Teraz w literaturze znalazłem tę pracę A. Gyárfás i D. Westa na wykresach interwałów wielościeżkowych, ale nie jestem pewien, czy ma to związek z powyższym problemem.

Przydałoby się cytowanie istniejącej literatury na temat powyższego lub podobnego problemu. Daj mi również znać, jeśli istnieje formalna nazwa powyższego problemu.

Myślę, że twój problem jest NP-zupełny. Jest to szczególny przypadek twierdzenia Farrugii , stwierdzającego, że trudno jest NP sprawdzić, czy zestaw wierzchołków graf można podzielić na dwa podzbiory i taki sposób, że należy do klasy grafów i należy do klasy grafów , pod warunkiem, że i są zamknięte przy przyjmowaniu związków rozłącznych od wierzchołków i mówieniu indukowanych podgrafów oraz przynajmniej jednego z i nie są trywialne (co oznacza, że ​​nie wszystkie wykresy w klasie są pozbawione krawędzi).$V_1,$$V_2$$G(V_1)$$\mathcal{P}$$G(V_2)$$\mathcal{Q}$$\mathcal{P}$$\mathcal{Q}$$\mathcal{P}$$\mathcal{Q}$