Charles Explorer logo
🇨🇿

Connected obstructions to full graph homomorphisms

Publikace na Matematicko-fyzikální fakulta |
2014

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

Minimal obstructions to full homomorphisms to a graph B have been proved to be of size at most |B| + 1. This turns out to require that disconnected obstructions be allowed.

In this paper we prove that the size of minimal connected obstructions is at most |B| + 2. We also prove that achieving |B| + 2 is rare and present a complete list of the exceptional cases.

Finally, we compute the dualities associated with these exceptions.