Graphs Having the Local Decomposition Property

Let \(H\) be a fixed graph without isolated vertices, and let \(G\) be a graph on \(n\) vertices. Let \(2 \leq k \leq n-1\) be an integer. We prove that if \(k \leq n-2\) and every \(k\)-vertex induced subgraph of \(G\) is \(H\)-decomposable, then \(G\) or its complement is either a complete graph or a complete bipartite graph. This also holds for \(k = n-1\) if all the degrees of the vertices of \(H\) have a common factor. On the other hand, we show that there are graphs \(H\) for which it is NP-Complete to decide if every \(n-1\)-vertex subgraph of \(G\) is \(H\)-decomposable. In particular, we show that \(H = K_{1,h-1}\), where \(h > 3\), are such graphs.