## 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_{2}(G) and g_{2}(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.

Original language | English |
---|---|

Pages (from-to) | 338-348 |

Number of pages | 11 |

Journal | Electronic Notes in Discrete Mathematics |

Volume | 11 |

DOIs | |

Publication status | Published - Jul 2002 |

Externally published | Yes |

## Keywords

- bicliques
- cliques
- homogeneously embeds
- k-edge-colouring
- stars
- uniformly embeds

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics