We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least (1 - 2/3 gamma(0)(G)) of its edges, where gamma(0)(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/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/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 >= 1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be ARX-hard for all k >= 2. However, approximation algorithms with approximation ratios tending to I as k goes to infinity are also known. At present, the best known performance ratios for the cases k = 2 and k = 3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k = 3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C(5)'s are also banned).

### Approximating the maximum 3-edge-colorable subgraph problem.

#### Abstract

We offer the following structural result: every triangle-free graph G of maximum degree 3 has 3 matchings which collectively cover at least (1 - 2/3 gamma(0)(G)) of its edges, where gamma(0)(G) denotes the odd girth of G. In particular, every triangle-free graph G of maximum degree 3 has 3 matchings which cover at least 13/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/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 >= 1, the Maximum k-Edge-Colorable Subgraph Problem asks to k-edge-color the most of the edges of a simple graph received in input. The problem is known to be ARX-hard for all k >= 2. However, approximation algorithms with approximation ratios tending to I as k goes to infinity are also known. At present, the best known performance ratios for the cases k = 2 and k = 3 were 5/6 and 4/5, respectively. Since the proofs of our structural result are algorithmic, we obtain an improved approximation algorithm for the case k = 3, achieving approximation ratio of 6/7. Better bounds, and allowing also for parallel edges, are obtained for graphs of higher odd girth (e.g., a bound of 13/15 when the input multigraph is restricted to be triangle-free, and of 19/21 when C(5)'s are also banned).
##### Scheda breve Scheda completa Scheda completa (DC)
2009
Approximation algorithm; Edge-coloring; 3-edge-coloring; Petersen graph; Odd girth
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11562/409556`
• ND
• 21
• 17