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
    Commented Apr 24, 2012 at 22:49
  • $\begingroup$ corrected now!! $\endgroup$
    – Turbo
    Commented 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
    Commented 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
    Commented Apr 24, 2012 at 23:26
  • $\begingroup$ @Gjergji Zaimi: Is there an inequality related to independence number? Do you have a reference? $\endgroup$
    – Turbo
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .