It is well-known that the GRAPH 3-COLORABILITY problem, deciding whether a
given graph has a stable set whose deletion results in a bipartite graph, i
s NP-complete. We prove the following related theorems: It is NP-compIete t
o decide whether a graph has a stable set whose deletion results in (1) a t
ree or (2) a trivially perfect graph, and there is a polynomial algorithm t
o decide if a given graph has a stable set whose deletion results in (3) th
e complement of a bipartite graph, (4) a split graph or (5) a threshold gra
ph. (C) 1998 Elsevier Science B.V. All rights reserved.