Hell, Pavol; Pultr, Aleš Connected obstructions to full graph homomorphisms. (English) Zbl 1300.05181 Eur. J. Comb. 41, 278-288 (2014). Summary: 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. Cited in 1 Document MSC: 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) Keywords:minimal connected obstructions PDFBibTeX XMLCite \textit{P. Hell} and \textit{A. Pultr}, Eur. J. Comb. 41, 278--288 (2014; Zbl 1300.05181) Full Text: DOI References: [1] Alon, N.; Pach, J.; Solymosi, J., Ramsey-type theorems with forbidden subgraphs, Combinatorica, 21, 155-170 (2001) · Zbl 0989.05124 [3] Ball, R. N.; Nešetřil, J.; Pultr, A., Dualities in full homomorphisms, European J. Combin., 31, 106-119 (2010) · Zbl 1219.05092 [4] Feder, T.; Hell, P., Full constraint satisfaction problems, SIAM J. Comput., 36, 230-246 (2006) · Zbl 1111.68115 [5] Feder, T.; Hell, P., On realizations of point determining graphs and obstructions to full homomorphisms, Discrete Math., 308, 1639-1652 (2008) · Zbl 1135.05042 [6] Feder, T.; Vardi, M., The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory, SIAM J. Comput., 28, 57-104 (1998) · Zbl 0914.68075 [7] Foniok, J.; Nešetřil, J.; Tardif, C., Generalized dualities and maximal finite antichains in the homomorphism order of relational structures, European J. Combin., 29, 881-899 (2008) · Zbl 1147.05037 [8] Hell, P., From graph colouring to constraint satisfaction: there and back again, (Topics in Discrete Mathematics, Algorithms and Combinatorics (2006), Springer Verlag) · Zbl 1116.05028 [9] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press: Oxford University Press Oxford · Zbl 1062.05139 [10] Hell, P.; Nešetřil, J., Colouring, constraint satisfaction, and complexity, Comp. Sci. Rev., 2, 143-164 (2008) · Zbl 1302.68251 [11] Komárek, P., Some new good characterizations for directed graphs, Časopis Pěst. Mat., 109, 348-354 (1984) · Zbl 0569.05022 [13] Mac Lane, S., Categories for the Working Mathematician (1971), Springer-Verlag: Springer-Verlag New York · Zbl 0232.18001 [14] Nešetřil, J.; Pultr, A., On classes of relations and graphs determined by subobjects and factorobjects, Discrete Math., 22, 287-300 (1978) · Zbl 0388.05039 [15] Nešetřil, J.; Tardif, C., Duality theorems for finite structures (characterizing gaps and good characterizations), J. Combin. Theory Ser. B, 80, 80-97 (2000) · Zbl 1024.05078 [16] Nešetřil, J.; Tardif, C., Short answers to exponentially long questions: extremal aspects of homomorphism duality, SIAM J. Discrete Math., 19, 914-920 (2005) · Zbl 1105.05025 [18] Sumner, D., Point determination in graphs, Discrete Math., 5, 179-187 (1973) · Zbl 0265.05124 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.