EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-ND 4.0

On Endomorphism Universality of Sparse Graph Classes

Kolja Knauer, Gil Puig i Surroca

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →