Vertex coverings by coloured induced graphs — Frames and Umbrellas

Abstract

A graph G homogeneously embeds in a graph H if for every vertex x of G and every vertex y of H there is an induced copy of G in H with x at y. The graph G uniformly embeds in H if for every vertex y of H there is an induced copy of G in H containing y. For positive integer k, let f _k(G) (respectively, g _k(G)) be the minimum order of a graph H whose edges can be k-coloured such that for each colour, G homogeneously embeds (respectively, uniformly embeds) in the graph given by V(H) and the edges of that colour. We investigate the values f ₂(G) and g ₂(G) for special classes of G, in particular when G is a star or balanced complete bipartite graph. Then we investigate f _k(G) and g _k(G) when k ≥ 3 and G is a complete graph.