On multicolored forests in complete bipartite graphs
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)].
- Multicolored forests in complete bipartite graphs
- Multicolored forests in bipartite decompositions of graphs
- Multicolored trees in complete graphs
- Multicolored trees in complete graphs
- Fork-forests in bi-colored complete bipartite graphs
- An f-chromatic spanning forest of edge-colored complete bipartite graphs
- scientific article; zbMATH DE number 1418267
- Cooperative colorings of trees and of bipartite graphs
- Multicolor Ramsey numbers for complete bipartite versus complete graphs
- scientific article; zbMATH DE number 139929
This page was built for publication: On multicolored forests in complete bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1879163)
