3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Shouldn't it be $\omega(G) \leq \omega(H)$? $\endgroup$
    – Felix Goldberg
    Apr 24, 2012 at 22:49
  • $\begingroup$ corrected now!! $\endgroup$
    – Turbo
    Apr 24, 2012 at 22:59
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gjergji Zaimi
    Apr 24, 2012 at 23:04
  • $\begingroup$ Hi the second part of the question is under what conditions, can one expect a homomorphism? $\endgroup$
    – Turbo
    Apr 24, 2012 at 23:26
  • $\begingroup$ @Gjergji Zaimi: Is there an inequality related to independence number? Do you have a reference? $\endgroup$
    – Turbo
    Apr 24, 2012 at 23:39

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$

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.