Title: 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 fk(G) (respectively, gk(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 f2(G) and g2(G) for special classes of G, in particular when G is a star or balanced complete bipartite graph. Then we investigate fk(G) and gk(G) when k ≥ 3 and G is a complete graph.
Publication Year: 2002
Publication Date: 2002-07-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot