Feder, Tomás; Hell, Pavol On realizations of point determining graphs, and obstructions to full homomorphisms. (English) Zbl 1135.05042 Discrete Math. 308, No. 9, 1639-1652 (2008). Summary: A graph is point determining if distinct vertices have distinct neighbourhoods. A realization of a point determining graph \(H\) is a point determining graph \(G\) such that each vertex-removed subgraph \(G-x\) which is point determining, is isomorphic to \(H\). We study the fine structure of point determining graphs, and conclude that every point determining graph has at most two realizations. A full homomorphism of a graph \(G\) to a graph \(H\) is a vertex mapping \(f\) such that for distinct vertices \(u\) and \(v\) of \(G\), we have \(uv\) an edge of \(G\) if and only if \(f(u)f(v)\) is an edge of \(H\). For a fixed graph \(H\), a full \(H\)-colouring of \(G\) is a full homomorphism of \(G\) to \(H\). A minimal \(H\)-obstruction is a graph \(G\) which does not admit a full \(H\)-colouring, such that each proper induced subgraph of \(G\) admits a full \(H\)-colouring. We analyse minimal \(H\)-obstructions using our results on point determining graphs. We connect the two problems by proving that if \(H\) has \(k\) vertices, then a graph with \(k+1\) vertices is a minimal \(H\)-obstruction if and only if it is a realization of \(H\). We conclude that every minimal \(H\)-obstruction has at most \(k+1\) vertices, and there are at most two minimal \(H\)-obstructions with \(k+1\) vertices.We also consider full homomorphisms to graphs \(H\) in which loops are allowed. If \(H\) has \(\ell \) loops and \(k\) vertices without loops, then every minimal \(H\)-obstruction has at most \((k+1)(\ell +1)\) vertices, and, when both \(k\) and \(\ell \) are positive, there is at most one minimal \(H\)-obstruction with \((k+1)(\ell +1)\) vertices. In particular, this yields a finite forbidden subgraph characterization of full \(H\)-colourability, for any graph \(H\) with loops allowed. Cited in 2 ReviewsCited in 14 Documents MSC: 05C62 Graph representations (geometric and intersection representations, etc.) 05C15 Coloring of graphs and hypergraphs 05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) 05C75 Structural characterization of families of graphs Keywords:point determining graphs; full homomorphisms; forbidden subgraph characterizations; polynomial algorithms PDFBibTeX XMLCite \textit{T. Feder} and \textit{P. Hell}, Discrete Math. 308, No. 9, 1639--1652 (2008; Zbl 1135.05042) Full Text: DOI References: [1] R.N. Ball, J. Nešetřil, A. Pultr, Dualities in full homomorphisms, Manuscript, 2006.; R.N. Ball, J. Nešetřil, A. Pultr, Dualities in full homomorphisms, Manuscript, 2006. [2] Entringer, R. C.; Gassman, L. D., Line-critical point determining and point distinguishing graphs, Discrete Math., 10, 43-55 (1974) · Zbl 0288.05125 [3] T. Feder, P. Hell, Matrix partitions of perfect graphs, Discrete Appl. Math. 306 (2006) 2450-2460.; T. Feder, P. Hell, Matrix partitions of perfect graphs, Discrete Appl. Math. 306 (2006) 2450-2460. · Zbl 1143.05035 [4] T. Feder, P. Hell, S. Klein, R. Motwani, Complexity of list partitions, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 464-472.; T. Feder, P. Hell, S. Klein, R. Motwani, Complexity of list partitions, in: Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 464-472. · Zbl 1345.68171 [5] Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Comput., 16, 449-478 (2003) · Zbl 1029.05143 [6] Feder, T.; Hell, P.; Klein, S.; Tito Nogueira, L.; Protti, F., List matrix partitions of chordal graphs, Theoret. Comput. Sci., 349, 52-66 (2005) · Zbl 1084.05026 [7] T. Feder, P. Hell, W. Xie, Matrix partitions with finitely many obstructions, Electronic Notes in Discrete Math. 28 (2007) 371- 378.; T. Feder, P. Hell, W. Xie, Matrix partitions with finitely many obstructions, Electronic Notes in Discrete Math. 28 (2007) 371- 378. · Zbl 1158.05325 [8] Geoffrey, D. P.; Sumner, D., The edge nucleus of a point-determining graph, J. Combin. Theory B, 24, 189-201 (1978) · Zbl 0382.05046 [9] P. Hell, From graph colouring to constraint satisfaction: there and back again, In: M. Klazar et al. (Eds.), Topics in Discrete Math., Dedicated to Jarik Nešetřil on the Occasion of his 60th Birthday, Vol. 26, Springer series, Algorithms and Combinatorics, Springer, Berlin, 2006, pp. 407-432.; P. Hell, From graph colouring to constraint satisfaction: there and back again, In: M. Klazar et al. (Eds.), Topics in Discrete Math., Dedicated to Jarik Nešetřil on the Occasion of his 60th Birthday, Vol. 26, Springer series, Algorithms and Combinatorics, Springer, Berlin, 2006, pp. 407-432. · Zbl 1116.05028 [10] Hell, P.; Nešetřil, J., On the complexity of \(H\)-colouring, J. Combin. Theory B, 48, 92-110 (1990) · Zbl 0639.05023 [11] Hell, P.; Nešetřil, J., Graphs and Homomorphisms (2004), Oxford University Press: Oxford University Press Oxford · Zbl 1062.05139 [12] Sumner, D., Point determination in graphs, Discrete Math., 5, 179-187 (1973) · Zbl 0265.05124 [13] Sumner, D., 1-factors of point determining graphs, J. Combin. Theory B, 16, 35-41 (1974) · Zbl 0284.05121 [14] Sumner, D., The nucleus of a point determining graph, Discrete Math., 14, 91-97 (1976) · Zbl 0326.05117 [15] W. Xie, Obstructions to trigraph homomorphisms, M.Sc. Thesis, Simon Fraser University, 2006.; W. Xie, Obstructions to trigraph homomorphisms, M.Sc. Thesis, Simon Fraser University, 2006. 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.