MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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. – András Salamon Jul 11 '12 at 8:28
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. – James Cranch Jul 11 '12 at 12:07
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. – András Salamon Jul 11 '12 at 13:07
Precisely so! Thanks. – James Cranch Jul 11 '12 at 13:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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