On multicolored forests in complete bipartite graphs (Q1879163)

Given a \(k\)-edge coloring (not necessarily proper) of a graph \(G\), its color distribution is the sequence \((a_1, \dots, a_k)\) where \(a_i\) is the number of edges of color \(i\) for \(i \in \{1, \dots, k\}\). A subgraph \(H\) of \(G\) is multicolored (according to given edge coloring) if all edges of \(H\) receive distinct colors. In the paper under review, it is proved that the complete bipartite graph \(K_{n,n+r}\) colored with the color distribution \((a_1, \dots, a_p)\) admits a partition into multicolored subgraphs of sizes \(2n - 1 + r, 2n - 3 + r, \dots, 1+r\) if and only if the sequence \((a_1, \dots , a_p)\) is majorized by the sequence \((1,1,2,2, \dots, n-1,n-1,n,n, \dots , n)\) with the last \(r+1\) terms equal to \(n\) (here the majorization is defined as follows: given \(p_1 \leq p_2 \leq \dots \leq p_k\) and \(q_1 \leq q_2 \leq \dots \leq q_k\), a sequence \(\mathbf{p} = (p_1,\dots, p_k)\) is majorized by \(\mathbf{q} = (q_1, \dots, q_k)\) if \(p_1 + \dots + p_i \geq q_1 + \dots + q_i\) for \(i = 1,\dots , k\) with equality when \(i=k\)). In addition, if \(0 \leq r \leq 1 + \sqrt{n}\), then \(K_{n,n+r}\) can be partitioned into multicolored forests of mentioned sizes. Further, if \(K_{n,n+r}\) has a color distribution \((a_1,a_2,\dots , a_{2n-1+r}),\;a_1 \leq a_2 \leq \dots \leq a_{2n-1+r}\), then every coloring of \(K_{n,n+r}\) with this distribution contains a multicolored spanning tree if and only if \(\sum_{i=1}^k a_i > \frac{k^2}{4}\) for every integer \(k \leq 2n-1+r\). These results extend the ones of \textit{R. A. Brualdi} and \textit{S. Hollingsworth} [Discrete Math. 240, 239--245 (2001; Zbl 0988.05038)].