# graph homomorphism

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?

-
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

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