On multicolored forests in complete bipartite graphs
type: Item
instance of: scholarly article
title: On multicolored forests in complete bipartite graphs
zbMATH Open document ID: 1058.05028
author: Bo Zhou
published in: Vietnam Journal of Mathematics
publication date: 2004-09-22T00:00:00Z
review text: 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)].
reviewed by: Tomáš Madaras
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 2101841
zbMATH Keywords: color distribution
zbMATH Keywords: multicolored subgraph
zbMATH Keywords: multicolored forest
MaRDI profile type: Publication
Recommended article: Multicolored forests in complete bipartite graphs
Recommended article: Multicolored forests in bipartite decompositions of graphs
Recommended article: Multicolored trees in complete graphs
Recommended article: Fork-forests in bi-colored complete bipartite graphs
Recommended article: An f-chromatic spanning forest of edge-colored complete bipartite graphs
Recommended article: Q4941827
Recommended article: Cooperative colorings of trees and of bipartite graphs
Recommended article: Multicolor Ramsey numbers for complete bipartite versus complete graphs
Recommended article: Q4028276
description: scientific article; zbMATH DE number 2101841