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



What can be said about graphs if there are homomorphisms in both directions?
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.


Two graphs such that each has a homomorphism to the other are *homomorphically equivalent*. This is an equivalence relation on the set of graphs, and the minimal representative of each equivalence class is called a *core*, which is unique up to isomorphism. Every endomorphism of a core is an isomorphism.


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


