  The homomorphism problem for relational structures is an abstract way of
formulating constraint satisfaction problems (CSP) and various problems in
database theory. The decision version of the homomorphism problem received a
lot of attention in literature; in particular, the way the graph-theoretical
structure of the variables and constraints influences the complexity of the
problem is intensively studied. Here we study the problem of enumerating all
the solutions with polynomial delay from a similar point of view. It turns out
that the enumeration problem behaves very differently from the decision
version. We give evidence that it is unlikely that a characterization result
similar to the decision version can be obtained. Nevertheless, we show
nontrivial cases where enumeration can be done with polynomial delay.
