Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a = (a(1), a(2), ... a(k)), in which a(i) denotes the number of edges of color i for i = 1, 2,..., k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K-n,K-n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K-n,K-n into multicolored trees. (C) 2001 Elsevier Science B.V. All rights reserved.