  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 several characterizations of a homomorphism dualities arising
in a class of structure.
