On recognizing graphs by numbers of homomorphisms

Let hom ( G, H ) be the number of homomorphisms from a graph G to a graph H . A well‐known result of Lovász states that the function hom (·, H ) from all graphs uniquely determines the graph H up to isomorphism. We study this function restricted to smaller classes of graphs. We show that several natural classes (2‐degenerate graphs and graphs homomorphic to an arbitrary non‐bipartite graph) are sufficient to recognize all graphs, and provide a description of graph properties that are recognizable by graphs with bounded tree‐width.