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 ( 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 mt 3 /ln t ≤ g ( m , K t ) ≤ c mt 3 /ln t , where c 1 , c 2 , c , c 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 .