List-homomorphism problems on graphs and arc consistency

We characterise the graphs (which may contain loops) whose list-homomorphism problem is solvable by arc consistency, or equivalently, that admit conservative totally symmetric idempotent operations of all arities. We prove that for every bipartite graph G , its list-homomorphism problem is tractable if and only if G admits a monochromatic conservative semilattice operation; in particular, its list-homomorphism problem can easily be solved by a combination of two-colouring and arc-consistency. We also present some results in this direction for the retraction problem on graphs.