# Graph Homomorphism and cliques

Let $G$ and $H$ be two graphs. It is known that if there is a homomorphism from $G$ to $H$, then $\omega(G) \leq \omega(H)$ where $\omega(G)$ is the clique number of $G$.

When does the converse hold and when does it fail?

-
A trivial example of the converse's failure would be to take $G$ to be a complete graph and $H$ to be an edgeless graph. –  Austin Mohr Jan 25 '13 at 4:02
It should be $\omega(G) \leq \omega(H)$, not $\geq$. –  polkjh Jan 25 '13 at 7:38
@polkjh Look at observation $2.6$ here (mast.queensu.ca/~ctardif/articles/ghss.pdf) –  Turbo Jan 25 '13 at 7:57
I think that is a mistake. Suppose there is a homomorphism from $G$ to $H$. Adding edges and vertices to $H$ retains the homomorphism from $G$ to $H$. So we can increase $\omega(H)$ indefinitely and still have a homomorphism from $G$ to $H$, which contradicts that $\omega(H)$ cannot be more than $\omega(G)$. –  polkjh Jan 25 '13 at 8:07

If $H$ is a subgraph of $G$, then there is a homomorphism $H\to G$. But clearly $\omega(H)$ can even be zero, while $\omega(H)$ could be as large as $|V(G)|$.

For the converse, there is no hope. As an example consider triangle-free graphs, with $\omega=2$. For each positive integer $m$, there are triangle-free graphs with chromatic number greater than $m$, and for such graphs there is no homomorphism to $K_m$.

-

Let $H=K_n$. Then existence of homomorphism from $G$ to $H$ implies $G$ is $n$-colorable. But $\omega(G) \leq n$ does not imply that $G$ is $n$-colorable (consider an odd cycle and $n=2$). So atleast for complete graphs $H$, the converse holds only if $\omega(H) \geq \chi(G)$ (chromatic number). This is not necessary for general graphs $H$. But I doubt there is any simple characterization of when the converse holds for generel $H$.

-
I think if a homomorphism from $G$ to $H = K_{n}$ exists, then $\omega(G) \geq n$ (mast.queensu.ca/~ctardif/articles/ghss.pdf observation $2.6$) –  Turbo Jan 25 '13 at 8:07
I think that might be a typo in the paper. Look at my comment above. –  polkjh Jan 25 '13 at 8:09
It might help if you try to prove the statement yourself (homomorphism from $G$ to $H$ implies $\omega(G) \leq \omega(H)$). It is not too difficult. –  polkjh Jan 25 '13 at 8:16