Abstract
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 polymorphism. This result mirrors the case for reflexive graphs and generalizes a known result for bipartite graphs which admit a 3-ary near-unanimity polymorphism.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Availability of Data and Material (Data Transparency)
Not applicable.
Code Availability (Software Application or Custom Code)
Not applicable.
References
Bandelt, H.J., Dahlmann, A., Schutte, H.: Absolute retracts of bipartite graphs. Discret. Appl. Math. 16, 121–215 (1987)
Bandelt, H.J.: Graphs with edge-preserving majority functions. Discret. Math. 103, 1–5 (1992)
Bandelt, H.J., Farber, M., Hell, P.: Absolute reflexive retracts and absolute bipartite retracts. Discret. Appl. Math. 44, 9–20 (1993)
Brewster, R., Feder, T., Hell, P., Huang, J., MacGillivray, G.: Near-unanimity functions and varieties of reflexive graphs. SIAM J. Discret. Math. 22, 938–960 (2008)
Brewster, R., MacGillivray, G.: Building blocks for the variety of absolute retracts. Discret. Math. 306, 1758–1764 (2006)
Feder, T., Hell, P., Larose, B., Loten, C., Siggers, M., Tardif, C.: Graphs admitting k-NU operations. Part 1: the reflexive case. SIAM J. Discret. Math. 27, 1639–2166 (2013)
Feder, T., Hell, P., Larose, B., Siggers, M., Tardif, C.: Graphs admitting k-NU operations. Part 2: the irreflexive case. SIAM J. Discret. Math. 28, 817–834 (2014)
Loten, C.: Retractions of chordal and related graphs. Ph.D thesis, Simon Fraser University, Burnaby, BC, Canada (2003)
Acknowledgements
I’m thankful for the guidance that my supervisor, Ross Willard, generously provided throughout the course of this research. I would like to acknowledge the support provided by the University of Waterloo and the National Science and Engineering Research Council of Canada.
Funding
This research was supported by NSERC (USRA-495080-2016).
Author information
Authors and Affiliations
Contributions
This work was completed by the sole author.
Corresponding author
Ethics declarations
Conflict of Interest
Not applicable.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Jaffe, A. Characterizing Bipartite Graphs Which Admit a k-NU Polymorphism via Absolute Retracts. Graphs and Combinatorics 37, 2459–2466 (2021). https://doi.org/10.1007/s00373-021-02367-w
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-021-02367-w