We find a set of generators of the variety of reflexive digraphs admitting $k-{NU}$ polymorphisms. We do this, in spite of the fact that such digraphs do not have finite tree duality, by defining finite duals of infinite trees. As a result of this, we answer a question of Quackenbush, Rival, and Rosenberg, giving a finite family of generators of the variety of finite bounded posets admitting $k-{NU}$ polymorphisms.

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.

We describe a generating set for the variety of reflexive graphs that admit a compatible $k$-ary near-unanimity (NU) operation. We further delineate a very simple subset that generates the variety of $j$-absolute retracts; in particular we show that the class of reflexive graphs with a 4-NU operation coincides with the class of 3-absolute retracts. Our results generalize and encompass several results on NU-graphs and absolute retracts.

In this paper, we present a new proof of the H-coloring dichotomy, which was first proved by Hell and Nešetřil in 1990, and then was reproved by Bulatov in 2005. Our proof is much shorter than the original proof and avoids the algebraic machinery of Bulatov's proof.

A graph G is r-Ramsey-minimal with respect to a graph H if every r-coloring of the edges of G yields a monochromatic copy of H, but the same is not true for any proper subgraph of G. In this paper we show that for any integer $k \geq 3$ and $r \geq 2$, there exists a constant $c>1$ such that for large enough n, there exist at least $c^{n^2}$ nonisomorphic graphs on at most n vertices, each of which is r-Ramsey-minimal with respect to the complete graph $K_k$. Furthermore, in the case $r=2$, we give an asymmetric version of the above result.