Does there exist a graph $G$ which cannot be properly vertex-coloured with 3 colours (i.e. $G$ has chromatic number at least 4), such that for every graph $H$, if $H$ contains a triangle but there is no graph homomorphism from $G$ to $H$, then $H$ must contain at least as many vertices as $G$?
This question arose from an application in computational complexity. Any pointers to similar results would be welcome, or a hint if this is trivial. I am familiar with Hell and Nešetřil's textbook Graphs and Homomorphisms and the classic constructions of rigid graphs by Chvátal et al. and Nešetřil/Rödl, but am not an expert in graph theoretic combinatorics.
Motivation
In some sense, this problem seeks a lower bound on the size of graphs $H$ which contain a triangle but which are also not homomorphic images of $G$. This compares to the usual Ramsey requirement, which can be phrased in terms of bounding the size of graphs which guarantee the presence of large enough complete subgraphs, or the absence of homomorphic images of large enough complete graphs.
The linear relationship between the order of $G$ and $H$ is the first "interesting" one. If the bound is decreased by 1, requiring only $|V(H)| \ge |V(G)| - 1$, then $G = K_4$ suffices but the size condition on $H$ holds simply because $H$ contains a triangle. I would also be interested in extensions, such as establishing whether such a graph $G$ exists for other functions bounding the order of $H$ in terms of the order of $G$.
