Karp hardness of testing for homomorphisms to a fixed non-bipartite graph Description: Suppose that we are given a fixed non-bipartite graph $H$. A graph $G$ is loopless surjectively homomorphic to $H$ if there exists a loopless surjective homomorphism $\varphi:V(G)\to V(H)$ such that:


  For every $u,v\in V(G)$,  $(\varphi(u)=\varphi(v))\lor(uv\in E(G)\implies\varphi(u)\varphi(v)\in E(H))$.


Note that we do not allow loops and multiple edges. This is just because $H$ is  a fixed simple undirected graph. So, mapping to the same vertices is good but remember to map to every vertex of $H$. This also does not put constraint on those vertices mapped to the same $H$-vertex. By standard definition, without a loop at that $H$-vertex, the set of $G$-vertices mapped to it needs to be an independent set.

We want to decide whether a given graph $G$ is loopless surjectively homomorphic to $H$. Note that for each fixed non-bipartite $H$, we have a decision problem, denoted by $\mathrm{HOMOMORPHIC}_H$.

Formally, for every fixed (i.e. not part of the input) non-bipartite graph $H$, $\mathrm{HOMOMORPHIC_H}$ is defined as below:


  Input: An undirected graph $G$
  
  Output: YES if $G$ is loopless surjectively homomorphic to $H$, otherwise NO


We want to know the computational complexity of this problem.
As others have pointed out in the comments, your definition of homomorphism is highly unusual. In particular, any function whose image is a single vertex is a homomorphism by your definition, thus trivializing the decision problem. The usual definition is as follows:

A homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $uv\in E(G)$ we have $\varphi(u)\varphi(v)\in E(H)$.

For the usual definition, the problem is known to be NP-complete for every non-bipartite $H$. The reference (according to Wikipedia) is Hell, Pavol; Nešetřil, Jaroslav (1990), "On the complexity of H-coloring", Journal of Combinatorial Theory Series B, 48 (1): 92–110. (For bipartite $H$, on the other hand, there is a homomorphism if and only if $G$ is bipartite. Thus the decision problem is just bipartiteness of $G$, which is in PTIME.)

A few other notion are somewhat halfway between your definition and the usual one:


A strong homomorphism from $G$ to $H$ is a function $\varphi:V(G)\to V(H)$ such that for all $u,v\in V(G)$ we have $uv\in E(G)$ if and only if $\varphi(u)\varphi(v)\in E(H)$.
An embedding from $G$ in $H$ is an injective homomorphism, that is a homomorphism $\varphi$ such that for all $u,v\in V(G)$ with $u\not=v$ we have $\varphi(u)\not=\varphi(v)$.
An induced subgraph mapping is an injective strong homomorphism.


[EDIT]

For each of these variants, the problem is in PTIME for fixed $H$.
When injectivity is required, one can reject an instance if $|V(G)|&gt;|V(H)|$, so only a finite set of graphs remains. For strong homomorphisms, we can have $\varphi(v)=\varphi(w)$ only if $v$ and $w$ have the same neighbours. Hence after some polynomial time preprocessing, we can again assume injectivity.