Approximating the maximum 3-edge-colorable subgraph problem

We offer the following structural result: every triangle-free graph GG of maximum degree 3 has 3 matchings which collectively cover at least (1−23γo(G)) of its edges, where γo(G)γo(G) denotes the odd girth of GG. In particular, every triangle-free graph GG of maximum degree 3 has 3 matchings which cover at least 13/1513/15 of its edges. The Petersen graph, where we can 3-edge-color at most 13 of its 15 edges, shows this to be tight. We can also cover at least 6/76/7 of the edges of any simple graph of maximum degree 3 by means of 3 matchings; again a tight bound.For a fixed value of a parameter k≥1k≥1, the Maximum kk-Edge-Colorable Subgraph Problem asks to kk-edge-color the most of the edges of a simple graph received in input. The problem is known to be APXAPX-hard for all k≥2k≥2. However, approximation algorithms with approximation ratios tending to 1 as kk goes to infinity are also known. At present, the best known performance ratios for the cases k=2k=2 and k=3k=3 were 5/65/6 and 4/54/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k=3k=3, achieving approximation ratio of 6/76/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/1513/15 when the input multigraph is restricted to be triangle-free, and of 19/2119/21 when C5C5’s are also banned).