Subset matching and edge coloring in bipartite graphs

The focus of this paper is on finding a matching in a bipartite graph such that a given subset of vertices are matched. This is called subset matching and generalizes perfect matchings. We prove a necessary and sufficient condition for the existence of a subset matching in bipartite graphs. The proof is algorithmic and based on combination of two matchings. Remarkably, the necessary and sufficient condition always holds when the subset is composed of the vertices with maximum degree. This in turn leads to a simple algorithm that finds an optimal edge coloring in bipartite graphs with no need to transform the bipartite graph into a regular one.