Universal targets for homomorphisms of edge-colored graphs

A connection between the acyclic coloring and the existence of universal graphs was first observed by Alon and Marshall (1998) [2]. One of their results is that for the class of planar graphs, the size of the smallest k-universal graph is between k3+3 and 5k4. Our results yield that there exists a constant c such that for all k, this size is bounded from above by ck3.