×

Graphs admitting \(k\)-NU operations. II: The irreflexive case. (English) Zbl 1298.05272

Summary: 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.
For Part I see [Zbl 1285.05152].

MSC:

05C75 Structural characterization of families of graphs
08B05 Equational logic, Mal’tsev conditions

Citations:

Zbl 1285.05152
PDFBibTeX XMLCite
Full Text: DOI