2024/09/22 by Mkrtchyan, Vahan
#05C15 #05C70 #05C85 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2409.15388
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 is 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 an NP-hardness result for a version of this problem where we have color constraints on vertices. In fact, we show that this version is NP-hard already in bipartite graphs of maximum degree three. In order to achieve the result, we establish a connection between our problem and the problem of construction of special maximum matchings considered in the Master thesis of the author and defended back in 2003.