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

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|cite|improve this question
Shouldn't it be $\omega(G) \leq \omega(H)$? – Felix Goldberg Apr 24 '12 at 22:49
corrected now!! – Turbo 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? – Turbo Apr 24 '12 at 23:26
@Gjergji Zaimi: Is there an inequality related to independence number? Do you have a reference? – Turbo Apr 24 '12 at 23:39
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|cite|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.