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

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