## Universal H-colorable Graphs Without A Given Configuration

### Authors: Paul A. Dreyer, Jr. , Christopher Malon, and Jaroslav Nesetril

ABSTRACT

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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1999/99-46.ps.gz