Publication at Faculty of Mathematics and Physics |
2014
Abstract
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.