Characterization of graphs $G$ where $G\in {\mathrm{obs}}^{\ast }(H)$ for some graph $H$

Abstract

A full-homomorphism from a graph $G$ to a graph $H$ is a function on vertex sets that preserves adjacency and non-adjacency of vertices. A graph $G$ is called a minimal $H$-obstruction if it has no full-homomorphism to $H$ but every proper vertex induced subgraph of $G$ does. Such graphs can have at most $|V(H)|+1$ vertices. The set of minimal $H$-obstructions on $|V(H)|+1$ vertices is denoted by $\mathrm{obs}\ast (H)$. In question 2 of the paper "Santiago Guzm{á}n-Pro, Full-homomorphisms to paths and cycles, Discrete Mathematics, 347(3):113800, 2024" it is asked if there is a characterization of those graphs $G$ that lie in $\mathrm{obs}\ast (H)$ for some graph $H$. In this paper, we give a complete answer to this question.

12 pages, 2 figures. Submitted for publication