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

CC BY-SA 4.0
2023-08-23T14:42:45.760Z
Excellent...thanks! I had suspected that this was the case but I couldn't come up with the keyword "$b$-matching". For the benefit of others reading this, an explicit reference is Theorem 21.9 in Volume A of Alexander Schrijver's book, *Combinatorial Optimization: Polyhedra and Efficiency*.
Timothy Chow
CC BY-SA 4.0
2023-08-22T23:36:20.883Z
2023-08-22T23:36:20.883Z
Chandra Chekuri
<p>Can the maximum <span class="math-container">$k$</span>-edge-colorable subgraph of a bipartite graph be found in polynomial time? Equivalently, can the maximum <span class="math-container">$k$</span>-colorable subgraph of the line graph of a bipartite graph be found in polynomial time?</p>
<p>The most relevant reference I have found is <a href="https://arxiv.org/abs/2001.09644" rel="nofollow noreferrer">The maximum <span class="math-container">$k$</span>-colorable subgraph problem and related problems</a>, by Sotirov et al., which mentions that the problem is polynomial-time solvable in special cases; e.g., in <a href="https://doi.org/10.1016/0020-0190(87)90107-4" rel="nofollow noreferrer">The maximum <span class="math-container">$k$</span>-colorable subgraph problem for chordal graphs</a>, Yannakakis and Gavril showed that the problem is solvable in polynomial time for chordal graphs if <span class="math-container">$k$</span> 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.</p>
<p>The paper <a href="https://doi.org/10.1016/j.dam.2018.10.013" rel="nofollow noreferrer">On maximum <span class="math-container">$k$</span>-edge-colorable subgraphs of bipartite graphs</a> 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.</p>

<cc.complexity-theory><graph-algorithms><graph-colouring><bipartite-graphs>
Complexity of maximum k-edge-colorable subgraph of a bipartite graph
Timothy Chow
# Complexity of maximum k-edge-colorable subgraph of a bipartite graph

(Asked by: username_0 on 2023-08-22)

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](https://arxiv.org/abs/2001.09644), 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](https://doi.org/10.1016/0020-0190(87)90107-4), 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](https://doi.org/10.1016/j.dam.2018.10.013) 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.

**Tags:** cc.complexity-theory, graph-algorithms, graph-colouring, bipartite-graphs

---

## 1 answers

### Answer by username_1 on 2023-08-22. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_0**: Excellent...thanks! I had suspected that this was the case but I couldn't come up with the keyword "$b$-matching". For the benefit of others reading this, an explicit reference is Theorem 21.9 in Volume A of Alexander Schrijver's book, *Combinatorial Optimization: Polyhedra and Efficiency*.  

---

