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.


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$.


1 Answer 1


I'm confused. Take $H$ to be the triangle. Since $G$ is not three-colourable, there is no map from $G$ to $H$, and $H$ contains a triangle.

  • $\begingroup$ Maybe my phrasing is unclear? Making H a triangle does not satisfy the size requirement, since G must have at least four vertices to have chromatic number > 3. The last paragraph discusses weakening the size requirement so that making H be the triangle does work. $\endgroup$ Jul 11, 2012 at 8:28
  • $\begingroup$ I do not understand your comment. For any graph $G$ which can't be four-coloured, especially a very large one, then you can take $H$ to be the triangle: there is no morphism from $G$ to $H$, $H$ contains a triangle, and $H$ does not contain at least as many vertices as $G$. So the answer is no. $\endgroup$ Jul 11, 2012 at 12:07
  • $\begingroup$ Ah, you are saying that for every candidate G, making H a triangle satisfies the antecedent, but makes the consequent false. You are right, the condition on H must be revised. $\endgroup$ Jul 11, 2012 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.