I've done some experimenting on a graph coloring problem with 20 nodes and 23 edges, coloring the nodes with 3 different colors.
Using FindInstance with Integer variables I can solve the problem in about 3 seconds. Using FindInstance with 3 Boolean variables on each node, I can solve the problem in about 1.5 seconds. Converting the problem to a mixed integer linear programming formulation with 3 binary variables on each node, I can solve the problem in 11 mSec using NMinimize. For the FindInstance approach with 3 Boolean variables on each node, I used the BooleanCountingFunction to generate the constraints that only one variable on each node is True and that at most one variable is True for the corresponding variables on nodes connected by edges.