Article ID Journal Published Year Pages File Type
4653511 European Journal of Combinatorics 2014 11 Pages PDF
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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,