Finding the homomorphism between two homomorphic graphs: what is the name of this problem?

The "graph homomorphism problem" can be stated as: given two graphs $$G$$ and $$H$$, determine if there exists a homomorphism $$f$$ such that $$f: G \rightarrow H$$. This is a famous problem that is well-known to be NP-complete.

Now I'm thinking about a related problem: given two homomorphic graphs $$G$$ and $$H$$, find $$f: G \rightarrow H$$. Does this problem have a name? Is its complexity class known?

• Your problem is not a decision problem. In particular, it cannot be NP-complete or NP-hard. Oct 22 '21 at 5:55
• Good point. Fixed my question Oct 22 '21 at 5:58

There are a couple of cases that we can dispose of straight away.

A self-edge on some vertex $$v$$ is an edge $$v \rightarrow v$$. If $$H$$ has even one vertex with a self-edge, then it's trivial to construct a homomorphism which maps all vertices to that vertex and all edges to that edge.

Similarly, if $$H$$ doesn't have a single vertex with a self-edge but $$G$$ has, no homomorphism exists.

Finally, we can deal with the case where $$G$$ has no self-edges. Then $$G$$ must be a chromatic graph: for some $$k$$, the vertices of $$G$$ can be assigned $$k$$ colours such that the start and end of each edge do not share the same colour.

Denote the complete graph with $$k$$ vertices by $$K_k$$.

Exercise: Show that a homomorphism $$f : G \rightarrow K_k$$ describes a $$k$$-colouring of $$G$$. Conversely, show that every $$k$$-colouring of $$G$$ can be represented as a homomorphism $$f : G \rightarrow K_k$$.

So any solution to your problem is also a solution to the $$k$$-colouring problem.

The decision problem of testing a mapping to see if it is a graph homomorphism is trivially in P. It follows that your problem is FNP-complete.