Two hardness results for the maximum 2-edge-colorable subgraph problem in bipartite graphs
<|reference_start|>Two hardness results for the maximum 2-edge-colorable subgraph problem in bipartite graphs: In this paper, we consider the maximum $k$-edge-colorable subgraph problem. In this problem we are given a graph $G$ and a positive integer $k$, the goal to take $k$ matchings of $G$ such that their union contains maximum number of edges. This problem is NP-hard in cubic graphs, and polynomial time solvable in bipartite graphs as we observe in our paper. We present two NP-hardness results for two versions of this problem where we have weights on edges or color constraints on vertices. In fact, we show that these versions are NP-hard already in bipartite graphs of maximum degree three. In order to achieve these results, we establish a connection between our problems and the problem of construction of special maximum matchings considered in the Master thesis of the author and defended back in 2003.<|reference_end|>
@article{mkrtchyan2024two,
    title={Two hardness results for the maximum 2-edge-colorable subgraph problem
  in bipartite graphs},
    author={Vahan Mkrtchyan},
    journal={arXiv preprint arXiv:2409.15388},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.15388},
    primaryClass={math.CO cs.DM}
}