# Universal graph homomorphisms

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, w\}\in E(G)$ implies $\{f(v), f(w)\} \in E(H)$.

We say that a graph homomorphism $u:G\to H$ is universal if for every graph homomorphism $f:G\to H$ there is $v \in V$ such that $f(v) = u(v)$.

Is the composition of two universal graph homomorphisms universal?

• Dec 11, 2014 at 19:52

Let $G_k=W_{2k+5}\cup W_{2k+1}$, where $W_k$ is the wheel with $k$ spokes. Then for $k\ge 3$, every homomorphism $G_k\to G_{k-1}$ fixes the hub of the smaller wheel as there is no homomorphism $W_{2k+1}\to W_{2k+3}$, and every homomorphism $W_{2k+1}\to W_{2k-1}$ fixes the hub.
Now let $\phi_k:G_k\to G_{k-1}$ be injective homomorphisms (so the bigger wheel goes to the bigger wheel, the smaller to the smaller). Each of these is universal by the argument above. But if you you combine $\phi_{k+1}$ and $\phi_{k}$, the resulting homomorphism $G_{k+1}\to G_{k-1}$ is not universal: just use a homomorphism that switches the wheels.