The complexity of some problems related to GRAPH 3-COLORABILITY

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.