2016/08/22 by Adam Jaffe, Jaffe, Adam
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1608.06350
openalex publication_date 2016/08/22 · arxiv created 2016/09/04 · arxiv updated 2016/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We first introduce the class of bipartite absolute retracts with respect to tree obstructions with at most k leaves. Then, using the theory of homomorphism duality, we show that this class of absolute retracts coincides exactly with the bipartite graphs which admit a (k+1)-ary near-unanimity (NU) polymorphism. This result mirrors the case for reflexive graphs and generalizes a known result for bipartite graphs admitting a 3-NU polymorphism.