# What can be said about graphs if there are homomorphisms in both directions?

Let $G,H$ be simple undirected graphs without loops such that there are graph homomorphisms $f_1:G\to H$ and $f_2: H\to G$.

An easy argument shows that we have $\chi(G) = \chi(H)$, even for graphs with infinite chromatic number.

What other conclusions can be made about $G, H$ if we know that there are graph homomorphisms in either direction?

Note: There need not be a graph homomorphism between two graphs. For instance, $\textrm{Hom}(G,K_2)=\emptyset$ iff $\chi(G) > 2$.

• I don't really know anything about this question, but I found this on Wikipedia. Dec 1 '14 at 13:01

Let $\omega (G)$ be the clique number of $G$ i.e. the largest $n$ such that $G$ contains $K_n$ as a subgraph; this is the same as the largest $n$ such that a homomorphism $K_n \rightarrow G$ exists. By composing $K_n \rightarrow G \xrightarrow{f_1} H$ we obtain $\omega (G) \leq \omega (H)$ and similarly in the other direction, so that the graphs also have the same clique number.
Thus $G$ and $H$ above have the same core, so if you further suppose $\chi (G) = \omega (G)=n$ then the core of $G$ and $H$ is $K_n$.