## DIMACS TR: 99-46

## 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

DIMACS Home Page