Amb motiu del tancament d'estiu, la validació de documents es reprendrà a partir del 28 d'agost de 2026. Disculpeu les molèsties.
Con motivo del cierre de verano, la validación de documentos se reanudará a partir del 28 de agosto de 2026. Disculpad las molestias
Due to the summer closure, document validation will resume starting August 28, 2026. We apologize for any inconvenience.

Fitxers

919381.pdf (1.15 MB)

Tipus de document

Article

Versió

Versió publicada

Data de publicació

2025-07-01

Llicència de publicació

cc by-nc-nd (c) Kolja Knauer et al., 2025
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/227127

On endomorphism universality of sparse graph classes.

Títol de la revista

Autors

Director/Tutor

ISSN de la revista

Títol del volum

Recurs relacionat

https://doi.org/10.1002/jgt.23262

Resum

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

Matèries

Isomorfismes (Matemàtica), Teoria de grafs, Representacions de semigrups

Matèries (anglès)

Isomorphisms (Mathematics), Graph theory, Representations of semigroups

Citació

Col·leccions

Articles publicats en revistes (Matemàtiques i Informàtica)

Citació

KNAUER, Kolja and PUIG I SURROCA, G. On endomorphism universality of sparse graph classes. Journal of Graph Theory. 2025. Vol. 110, num. 2, pags. 223-244. ISSN 0364-9024. [consulted: 11 of August of 2026]. Available at: https://hdl.handle.net/2445/227127

Exportar metadades

JSON - METS

Compartir registre