On Endomorphism Universality of Sparse Graph Classes

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