Premium
On recognizing graphs by numbers of homomorphisms
Author(s) -
Dvořák Zdeněk
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20461
Subject(s) - combinatorics , mathematics , discrete mathematics , graph homomorphism , chordal graph , cograph , pathwidth , graph isomorphism , indifference graph , pancyclic graph , graph product , line graph , bipartite graph , homomorphism , graph , voltage graph
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. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 330–342, 2010