On realizations of point determining graphs, and obstructions to full homomorphisms

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-xG-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 vv of G  , we have uvuv an edge of G   if and only if f(u)f(v)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+1k+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+1k+1 vertices, and there are at most two minimal H  -obstructions with k+1k+1 vertices.We also consider full homomorphisms to graphs H in which loops are allowed. If H   has ℓℓ loops and k vertices without loops, then every minimal H  -obstruction has at most (k+1)(ℓ+1)(k+1)(ℓ+1) vertices, and, when both k   and ℓℓ are positive, there is at most one minimal H  -obstruction with (k+1)(ℓ+1)(k+1)(ℓ+1) vertices.In particular, this yields a finite forbidden subgraph characterization of full H-colourability, for any graph H with loops allowed.