Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653511 | European Journal of Combinatorics | 2014 | 11 Pages |
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
Pavol Hell, Aleš Pultr,