We address the following problem: what classes C admit first-order definable H-colorings, that is H-colorings problems equivalent *in the class* to the satisfaction of a formula expressed in first-order logic. We relate the existence of such first-order definable coloring problems to the concept of classes of bounded expansion, and propose a conjecture linked to a weakening of a conjecture by Erdos and Hajnal and to a conjecture due to Thomassen.