b-matchings

The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a … Read more