## Abstract

We consider a canonical Ramsey type problem. An edge-coloring of a graph is called m-good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m-good edge-coloring of K _{n} yields a properly edge-colored copy of G, and let g(m, G) denote the smallest n such that every m-good edge-coloring of K _{n} yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = K _{t} we have c _{1} mt ^{2}/ln t ≤ f(m, K _{t}) ≤ c _{2}mt ^{2}, and c′ _{1}mt ^{3}/ln t ≤ g(m, K _{t}) ≤ c′ _{2}mt ^{3}/ln t, where c _{1}, c _{2}, c′ _{1}, c′ _{2} are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d.

Original language | English (US) |
---|---|

Pages (from-to) | 409-433 |

Number of pages | 25 |

Journal | Random Structures and Algorithms |

Volume | 23 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2003 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Software
- General Mathematics
- Computer Graphics and Computer-Aided Design
- Applied Mathematics