Maltsev digraphs have a majority polymorphism
arXiv:0912.4035 · doi:10.1016/j.ejc.2010.11.002
Abstract
We prove that when a digraph has a Maltsev polymorphism, then also has a majority polymorphism. We consider the consequences of this result for the structure of Maltsev graphs and the complexity of the Constraint Satisfaction Problem.
8 pages, 4 figures; minor changes (stylistics, elsarticle LaTeX style, citations); submitted to European Journal of Combinatorics
Cited by in corpus (7)
- A finer reduction of constraint problems to digraphs
- Asking the metaquestions in constraint tractability
- Digraphs Homomorphism Problems with Maltsev Condition
- Binarisation for Valued Constraint Satisfaction Problems
- The Smallest Hard Trees
- Digraph homomorphism problem and weak near unanimity polymorphism
- Second order conservative languages with a Maltsev polymorphism also have a majority polymorphism