Edge-Colorings with No Large Polychromatic Stars

 Given a graph G and a positive integer r, let f _r (G) denote the largest number of colors that can be used in a coloring of E(G) such that each vertex is incident to at most r colors. For all positive integers n and r, we determine f _r (K _n,n ) exactly and f _r (K _n ) within 1. In doing so, we disprove a conjecture by Manoussakis, Spyratos, Tuza and Voigt in [4]. Received: May 17, 1999 Final version received: January 12, 2000