Homomorphisms are a good basis for counting small subgraphs
Radu Curticapean, Holger Dell, Dániel Marx · 2017
We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G.