Two graphs $G,H$ are homomorphically equivalent if there are exists a homomorphism from $G$ to $H$ and a homomorphism from $H$ to $G$.
The task is to prove that this decision problem $\mathrm{HOMEQUIV}$ is $NP$-complete.
Given a mapping $G \to H$ (or $H \to G$) it is possible to check whether it is an homomorphism in polynomial time. Thus, $\mathrm{HOMEQUIV} \in NP$.
Now I am looking for a suitable $NP$-complete problem with an elegant polynomial reduction to $\mathrm{HOMEQUIV}$. I was thinking about $\mathrm{3SAT}$ but I did not come up with a solution up until now.
There is a reduction to $3 ~ \mathrm{COLORING}$ which is pretty easy and I know from internet research that $\mathrm{3SAT} \leq_p 3 ~ \mathrm{COLORING}$. But I think this is cheating somehow because it is not a direct proof and it lacks the complicated part ($\mathrm{3SAT} \leq_p 3 ~ \mathrm{COLORING}$).
Any ideas for an elegant reduction?