For every pair of finite connected graphs $F$ and $H$, and every integer $k$, we construct a universal graph $U$ with the following properties:
\begin{enumerate} \item There is a homomorphism $\pi :U \ra H$, but no homomorphism from $F$ to $U$. \item For every graph $G$ with maximal degree no more than $k$ having a homomorphism $h:G \ra H$, but no homomorphism from $F$ to $G$, there is a homomorphism $\alpha :G \ra U$, such that $h = \pi \circ \alpha$. \end{enumerate}
Particularly, this solves a problem regarding the chromatic number of a universal graph.
DIMACS Home Page