Abstract
We address the problem of characterizing H-coloring problems that are first-order definable on a fixed class of relational structures. In this context, we give also several characterizations of a homomorphism dualities arising in a class of structures.