Complexity of maximum k-edge-colorable subgraph of a bipartite graph

Question

Can the maximum $k$-edge-colorable subgraph of a bipartite graph be found in polynomial time? Equivalently, can the maximum $k$-colorable subgraph of the line graph of a bipartite graph be found in polynomial time?

The most relevant reference I have found is The maximum $k$-colorable subgraph problem and related problems, by Sotirov et al., which mentions that the problem is polynomial-time solvable in special cases; e.g., in The maximum $k$-colorable subgraph problem for chordal graphs, Yannakakis and Gavril showed that the problem is solvable in polynomial time for chordal graphs if $k$ is fixed. Like chordal graphs, line graphs of bipartite graphs are perfect, but the references listed by Sotirov et al. don't seem to address the case of line graphs of bipartite graphs, unless I'm missing something.

The paper On maximum $k$-edge-colorable subgraphs of bipartite graphs by Karapetyan and Mkrtchyan specifically considers the subgraphs of interest to me, but they are interested in structural questions rather than computational complexity. Again, their paper, and the papers they cite regarding computational complexity, don't seem to answer my question, unless I'm missing something.

Answer 1

A bipartite multigraph is $k$-edge colorable iff the maximum degree of any vertex is at most $k$. So we are asking for a subgraph $H=(V,F)$ of a given bipartite graph $G=(V,E)$ such that $\delta_H(v) \le k$ for all $v \in V$ and we wish to maximize $|F|$. We can write an LP relaxation for this via variables $x_e, e \in E$ as follows: $\max \sum_e x_e$ subject to $x_e \in [0,1], e \in E$ and $\sum_{e \in \delta(v)} x_e \le k \forall v \in V$. This LP is integral because the graph is bipartite and hence we can solve the problem in polynomial-time. We are basically solving a $b$-matching problem.