# Homomorphical Equivalence is NP-complete

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?

• There are numerous references showing that 3SAT reduces to 3COLORING, e.g. here or here. – rphv May 16 '13 at 18:13

David Eppstein provides a nice reduction from $\mathrm{CLIQUE}$ to $3 \mathrm{COLORING}$ such that
Given a graph $G$, we construct another graph $H$ such that $H$ is $n$-colorable if and only if $G$ has a $k$-Clique.