Computing the number of induced copies of a fixed graph in a bounded degree graph

Viresh Patel, Guus Regts

In this paper we show that for any graph $H$ of order $m$ and any graph $G$ of order $n$ and maximum degree $\Delta$ one can compute the number of subsets $S$ of $V(G)$ that induces a g…