In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph
vertices with a color (or label) function
}, the labeled maximum matching problem consists in finding a maximum matching on
that uses a minimum or a maximum number of colors.