Universal targets for homomorphisms of edge-colored graphs

Grzegorz Guśpiel, Grzegorz Gutowski

Published 2015-08-26Version 1

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 color of every edge is preserved over the mapping. Given a class of graphs $\mathcal{F}$, 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}$ maps homomorphically 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. The main results are the following. A class of graphs $\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, the size of the smallest $k$-universal graph is $\Omega\left(k^{D(\mathcal{F})}\right)$ and $O\left(k^{\left\lceil D(\mathcal{F})\right\rceil}\right)$, where $D(\mathcal{F})$ is the maximum ratio of the number of edges to the number of vertices ranging over all subgraphs of all graphs in $\mathcal{F}$. 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 the class of planar graphs, the size of the smallest $k$-universal graph is between $k^3+3$ and $5k^4$. Our results yield that this size is $\Theta\left(k^3\right)$.