Deciding graph homomorphism Deciding Graph Homomorphism is in general NP-Complete.

Are there any results which study this problem when the underlying graphs have algebraic structure (such as deciding homomorphisms from Cayley or Cayley coset graphs to other graphs with some definite structure as well)? In addition complexity results I am also interested in helpful algebraic and/or spectral techniques.
If $\mathcal{G}$ is a class of graphs with bounded treewidth, then the homomorphism problem from graphs in $\mathcal{G}$ is polynomial-time solvable. This can be generalized to the more general property of "graphs whose core has bounded treewidth."

Grohe proves a converse: if the cores of the graphs in $\mathcal{G}$ have unbounded treewidth, then the homomorphism problem from $\mathcal{G}$ is not polynomial-time solvable (assuming $FPT\neq W[1]$). Therefore, if you restrict the left-hand side graph to Cayley graphs etc., then what matters is whether the cores have bounded treewidth.

http://dl.acm.org/authorize?951212

Note that this does not completely answer your question: in the result of Grohe, it is  assumed that the right-hand side graph is arbitrary. You seem to be interested in results where the right-hand side graph is also restricted to some specific class of graphs.