Abstract

We consider a generalization of edge coloring bipartite graphs in which every edge has a weight in [0,1] and the coloring of the edges must satisfy that the sum of the weights of the edges incident to a vertex v of any color must be at most 1. For unit weights, König's theorem says that the number of colors needed is exactly the maximum degree. For this generalization, we show that 2.557n + o(n) colors are sufficient, where n is the maximum total weight adjacent to any vertex, improving the previously best bound of 2.833n + O(1) due to Du et al. Our analysis is interesting on its own and involves a novel decomposition result for bipartite graphs and the introduction of an associated continuous one-dimensional bin packing instance which we can prove allows perfect packing. This question is motivated by the question of the rearrangeability of 3-stage Clos networks. In that context, the corresponding parameter n of interest in the edge coloring problem is the maximum over all vertices of the number of unit-sized bins needed to pack the weights of the incident edges. In that setting, we are able to improve the bound to 2.5480n + o(n), also improving a bound of 2.5625n + O(1) of Du et al. We also consider the online version of this problem in which edges have to be colored as soon as they are revealed. In this context, we can show that 5n colors are enough. This contrasts with the best known lower bound of 3n - 2 by Tsai, Wang, and Hwang but improves upon the previous best upper bound of 5.75n obtained by Gao and Hwang. Additionally, we show several improved bounds for more restricted versions of the problem. These online bounds are achieved by simple and easy-to-implement algorithms, inspired by the first fit heuristic for bin packing. ©2007 Society for Industrial and Applied Mathematics.