## On empty Hom-sets between graphs

In many categories such as Set, Group, Top (topological spaces) there is a morphism between any two objects, usually in both directions. (If one object is “empty”, like the empty space, or the empty set, there is the “empty” morphism from $\emptyset$ to the other object, but not the other way round.)

However in the category Graph it is possible that non-empty graphs $G,H$ have no graph homomorphism between them in either direction:

Let $K_3$ be the complete graph on 3 points and let $H$ be any triangle-free graph with $\chi(H) > 3$, for instance the Grötzsch graph, which has chromatic number 4.

Since $H$ is triangle-free, there is no graph homomorphism $\varphi: K_3 \to H$ and if there were a homomorphism $\eta : H \to K_3$, this map would be an $n$-coloring of $H$ for some $n \leq 3$.

Advertisements

## About dominiczypen

I'm interested in general topology, order theory, and graph theory. This link takes you to my preprints on arXiv.
This entry was posted in Uncategorized. Bookmark the permalink.