Publication at Faculty of Mathematics and Physics |
2010
Abstract
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.