Graphs Having the Local Decomposition Property

Abstract

Let $H$ be a fixed graph without isolated vertices, and let $G$ be a graph on $n$ vertices. Let $2\le k\le n-1$ be an integer. We prove that if $k\le 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.