List-Homomorphism Problems on Graphs and Arc Consistency
Benoît Larose, A. Lemaitre · 2012
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 semi lattice operation, in particular, its list-homomorphism problem can easily be solved by a combination of two-colouring and arc-consistency.