Approximating the maximum 2- and 3-edge-colorable subgraph problems

For a fixed value of a parameter k≥2k≥2, the Maximum kk-Edge-Colorable Subgraph Problem consists in finding kk edge-disjoint matchings in a simple graph, with the goal of maximising the total number of edges used. The problem is known to be APX-hard for all kk, but there exist polynomial time approximation algorithms with approximation ratios tending to 1 as kk tends to infinity. Herein we propose improved approximation algorithms for the cases of k=2k=2 and k=3k=3, having approximation ratios of 5/6 and 4/5, respectively.