  A $k$-edge-colored graph is a finite, simple graph with edges labeled by
numbers $1,\ldots,k$. A function from the vertex set of one $k$-edge-colored
graph to another is a homomorphism if the endpoints of any edge are mapped to
two different vertices connected by an edge of the same color. Given a class
$\mathcal{F}$ of graphs, a $k$-edge-colored graph $\mathbb{H}$ (not necessarily
with the underlying graph in $\mathcal{F}$) is $k$-universal for $\mathcal{F}$
when any $k$-edge-colored graph with the underlying graph in $\mathcal{F}$
admits a homomorphism to $\mathbb{H}$. We characterize graph classes that admit
$k$-universal graphs. For such classes, we establish asymptotically almost
tight bounds on the size of the smallest universal graph.
  For a nonempty graph $G$, the density of $G$ is the maximum ratio of the
number of edges to the number of vertices ranging over all nonempty subgraphs
of $G$. For a nonempty class $\mathcal{F}$ of graphs, $D(\mathcal{F})$ denotes
the density of $\mathcal{F}$, that is the supremum of densities of graphs in
$\mathcal{F}$.
  The main results are the following. The class $\mathcal{F}$ admits
$k$-universal graphs for $k\geq2$ if and only if there is an absolute constant
that bounds the acyclic chromatic number of any graph in $\mathcal{F}$. For any
such class, there exists a constant $c$, such that for any $k \geq 2$, the size
of the smallest $k$-universal graph is between $k^{D(\mathcal{F})}$ and
$ck^{\lceil D(\mathcal{F})\rceil}$.
  A connection between the acyclic coloring and the existence of universal
graphs was first observed by Alon and Marshall (Journal of Algebraic
Combinatorics, 8(1):5-13, 1998). One of their results is that for planar
graphs, the size of the smallest $k$-universal graph is between $k^3+3$ and
$5k^4$. Our results yield that there exists a constant $c$ such that for all
$k$, this size is bounded from above by $ck^3$.
