A t-round χ-coloring is defined as a sequence ψ_1, …, ψ_t of t (not necessarily distinct) edge colorings of a complete graph, using at most χ colors in each of the colorings. For positive integers k≤n and t let χ~t (k,n) denote the minimum number χ of colors for which there exists a t-round χ-coloring of K_n such that all (_2~k) edges of each K_k K_n get different colors in at least one round. Generalizing a result of J. Korner and G. Simonyi (1995, Studia Sci. Math. Hungar. 30, 95-103), it is shown in this paper that χ~t (3,n) = Θ(n~(1/t)). Two-round colorings for k＞3 are also investigated. Thight bounds are obtained for χ~2 (k,n) for all values of k except for k=5. We also study an inverted extremal function, t(k,n), which is the minimum number of rounds needed to color the edges of K_n with the same (_2~k) colors such that all (_2~k) edges of each K_k K_n get diffierent colors in at least one round. For k = n/2, t(k,n) is shown to be exponentially large. Several related questions are investigated. The discussed problems relate to perfect hash functions.
展开▼
