On Endomorphism Universality of Sparse Graph Classes
Journal of Graph Theory · 2025-10 · 110 (2) · 223-244
DOI: 10.1002/jgt.23262 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 11.06.2025. Verfasst von Kolja Knauer und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 48 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-ND 4.0).
Abstract (Originalsprache)
We show that every commutative idempotent monoid (a.k.a. lattice) is the endomorphism monoid of a subcubic graph. This solves a problem of Babai and Pultr and the degree bound is best‐possible. On the other hand, we show that no class excluding a minor can have all commutative idempotent monoids among its endomorphism monoids. As a by‐product, we prove that monoids can be represented by graphs of bounded expansion (reproving a result of Nešetřil and Ossona de Mendez) and ‐cancellative monoids can be represented by graphs of bounded degree. Finally, we show that not all completely regular monoids can be represented by graphs excluding topological minor (strengthening a result of Babai and Pultr).
Zitieren
APA
Knauer, K., & Surroca, G. P. I. (2025). On Endomorphism Universality of Sparse Graph Classes. Journal of Graph Theory, 110(2), 223-244. https://doi.org/10.1002/jgt.23262
Vancouver
Knauer K, Surroca GPI. On Endomorphism Universality of Sparse Graph Classes. Journal of Graph Theory. 2025;110(2):223-244. doi:10.1002/jgt.23262
BibTeX
@article{Knauer2025,
author = {Knauer, Kolja and Surroca, Gil Puig i},
title = {On Endomorphism Universality of Sparse Graph Classes},
journal = {Journal of Graph Theory},
year = {2025},
volume = {110},
number = {2},
pages = {223--244},
doi = {10.1002/jgt.23262}
}
EUVIMED