Graphs Admitting $k$-NU Operations. Part 2: The Irreflexive Case
Tomás Feder, Pavol Hell, Benoît Larose, Mark Siggers, Claude Tardif · SIAM Journal on Discrete Mathematics · 2014
We describe a generating set for the variety of simple graphs that admit a $k$-ary near-unanimity (NU) polymorphism. The result follows from an analysis of NU polymorphisms of strongly bipartite digraphs, i.e., whose vertices are either a source or a sink. We show that the retraction problem for a strongly bipartite digraph ${\mathbb H}$ has finite duality if and only if ${\mathbb H}$ admits an NU polymorphism. This result allows the use of tree duals to generate the variety of digraphs admitting a $k$-NU polymorphism.