Anti-Ramsey colorings in several rounds

A t-round chi -coloring is defined as a sequence psi (1),...,psi (t) of t ( not necessarily distinct) edge colorings of a complete graph, using at most chi colors in each of the colorings. For positive integers k less than or equal to n and t let chi (t)(k, n) denote the minimum number chi of colors for which there exists a t-round chi -coloring of K-n such that all ((k)(2) ) edges of each K-k subset of or equal to K-n get different colors in at le ast one round. Generalizing a result of J. Korner and G. Simonyi (1995, Stu dia Sci. Math. Hungar. 30, 95-103), it is shown in this paper that chi (t)( 3,n) = Theta (n(1/t)). Two-round colorings for k>3 are also investigated. T ight bounds are obtained for chi (2)(k, n) for all values of ic except for k = 5. We also study an inverted extremal function, t(k, n), which is the m inimum number of rounds needed to color the edges of K-n with the same ((k) (2)) colors such that all ((k)(2)) edges of each K-k subset of or equal to K-n get different colors in at least one round. For k = n/2, t(k, n) is sho wn to be exponentially large. Several related questions are investigated. T he discussed problems relate to perfect hash functions. (C) 2001 Academic P ress.