Negative Results on the Stability Problem Within Co-Hereditary Classes

Let \( S \) be a stable set in a graph \( G \), possibly \( S = \emptyset \). The subgraph \( G – N[S] \), where \( N[S] \) is the closed neighborhood of \( S \), is called a \emph{co-stable subgraph} of \( G \). We denote by \( \text{CSub}(G) \) the set of all co-stable subgraphs of \( G \). A class of graphs \( \mathcal{P} \) is called \emph{co-hereditary} if \( G \in \mathcal{P} \) implies \( \text{CSub}(G) \subseteq \mathcal{P} \). Our result: If the set of all minimal forbidden co-stable subgraphs for a non-empty co-hereditary class \( \mathcal{P} \) is finite, then Stable Set is an NP-complete problem within \( \mathcal{P} \). Also, we prove that the decision problem of recognizing whether a graph has a fixed graph \( H \) as a co-stable subgraph is NP-complete for each non-trivial graph \( H \).