ProV Logo
0
Universal targets for homomorphisms of e...
Guśpiel, Grzegorz...

Free

Universal targets for homomorphisms of edge-colored graphs by Guśpiel, Grzegorz ( Author )
Lemonjar Open Access
N.A
26-08-2015
A k-edge-colored graph is a finite, simple graph with edges labeled by numbers 1,…,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 F of graphs, a k-edge-colored graph H (not necessarily with the underlying graph in F) is k-universal for F when any k-edge-colored graph with the underlying graph in F admits a homomorphism to 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 F of graphs, D(F) denotes the density of F, that is the supremum of densities of graphs in F. The main results are the following. The class F admits k-universal graphs for k≥2 if and only if there is an absolute constant that bounds the acyclic chromatic number of any graph in F. For any such class, there exists a constant c, such that for any k≥2, the size of the smallest k-universal graph is between kD(F) and ck⌈D(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 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.
-
Article
pdf
36.88 KB
English
-
MYR 0.00
-
https://arxiv.org/abs/1508.06454
Share this eBook