  Minimum cost homomorphism problems can be viewed as a generalization of list
homomorphism problems. They also extend two well-known graph colouring
problems: the minimum colour sum problem and the optimum cost chromatic
partition problem. In both of these problems, the cost function meets an
additional constraint: the cost of using a specific colour is the same for
every vertex of the input graph. We study minimum cost homomorphism problems
with cost functions constrained to have this property. Clearly, when the
standard minimum cost homomorphism problem is polynomial, then the problem with
constrained costs is also polynomial. We expect that the same may hold for the
cases when the standard minimum cost homomorphism problem is NP-complete. We
prove that this is the case for trees $H$: we obtain a dichotomy of minimum
constrained cost homomorphism problems which coincides with the dichotomy of
standard minimum cost homomorphism problems. For general graphs $H$, we prove a
partial dichotomy: the problem is polynomial if $H$ is a proper interval graph
and NP-complete when $H$ is not chordal bipartite.
