Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints

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(In, G). For complete graphs G = K-t, we have c(1)mt(2)/ln t less than or equal to f(m, K-t) less than or equal to c(2)mt(2), and c'(1)mt(3)/ln t less than or equal to g(m, K-t) less than or equal to 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. (C) 2003 Wiley Periodicals, Inc.