A 2 edge-colorable graph is a graph in which we can color the edges with two colors, in a way such that no edges of the same color share a vertex. Given a graph G = (V,E) I want to find a 2 edge-colorable subgraph of G that has the maximum number of edges. Currently i am using this algorithm. I find a maximum size matching M1 in G and then I find a maximum size matching M2 in G - M1. I would like to show that this algorithm can grant me a 3/4 approximation of this problem. Can anyone help me proving that?

  • $\begingroup$ It should not be hard if true, but how do you guess this constant $3/4$ without having a proof? $\endgroup$ – Fedor Petrov Jan 12 '16 at 13:45
  • $\begingroup$ basically this problem can be seen as a special case of the maximum coverage problem, which for this problem would return this approximation. Can you help me? $\endgroup$ – Student Jan 12 '16 at 14:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.