Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $G$ and $H$ be two non-bipartite graphs. We know that, if $\exists$ homomorphism $\phi : G \rightarrow H$, then $\omega(G) \le \omega(H)$ where $\omega$ is clique number.

$(1)$ Does the converse hold in general?

$(2)$ Under what conditions does the converse hold?

share|improve this question
Shouldn't it be $\omega(G) \leq \omega(H)$? –  Felix Goldberg Apr 24 '12 at 22:49
corrected now!! –  J.A Apr 24 '12 at 22:59
Notice that there are similar inequalities for the chromatic number, independence number, odd girth etc. Even if all these are satisfied, a homomorphism is still not guaranteed. –  Gjergji Zaimi Apr 24 '12 at 23:04
Hi the second part of the question is under what conditions, can one expect a homomorphism? –  J.A Apr 24 '12 at 23:26
@Gjergji Zaimi: Is there an inequality related to independence number? Do you have a reference? –  J.A Apr 24 '12 at 23:39

1 Answer 1

up vote 7 down vote accepted

You have your inequality backwards, I believe.

If $\omega(G) \le \omega(H)$, it does not follow in general that there is a homomorphism from $G\to H$. There are many triangle-free graphs with chromatic number greater than four, none of these will admit a homomorphism to $K_4$.

share|improve this answer

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.