Given a countable graph $\mathcal{G}$ and a finite graph $\mathrm{H}$, we consider $\mathrm{Hom}(\mathcal{G},\mathrm{H})$ the set of graph homomorphisms from $\mathcal{G}$ to $\mathrm{H}$ and we study Gibbs measures supported on $\mathrm{Hom}(\mathcal{G},\mathrm{H})$ . We develop some sufficient and other necessary conditions on $\mathrm{Hom}(\mathcal{G},\mathrm{H})$ for the existence of Gibbs specifications satisfying strong spatial mixing (with exponential decay rate). We relate this with previous work of Brightwell and Winkler, who showed that a graph $\mathrm{H}$ has a combinatorial property called dismantlability if and only if for every $\mathcal{G}$ of bounded degree, there exists a Gibbs specification with unique Gibbs measure. We strengthen their result by showing that this unique Gibbs measure can be chosen to have weak spatial mixing, but we also show that there exist dismantlable graphs for which no Gibbs measure has strong spatial mixing.