I have a graph with the edges already assigned colors and there are edges of the same color as well as different colors incident to each vertex. I would like to find an edge cover (does not have to be minimal) such that no two different colored edges of the edge cover are incident to the same vertex. I thought about trying to extend a maximal matching, but then some of those edges of the matching might have to change to accommodate the unmatched vertices. I also thought about somehow assigning weights to the colors and changing it into an assignment problem, but this also doesn't seem to be sufficient since higher weighted colors can be used as many times as required as long as the condition (of different colored/weighted edges not incident to one another) is fulfilled. Any suggestions or hints?

  • $\begingroup$ Given your graph $G$, it's possible to build a new graph $G^*=(V^*,E^*)$ where $V^*$ is the set of edges from $G$, and we add $(x,y)$ to $E^*$ if edges $x,y$ are incident on the same vertex. If we then rephrase your question as a question about $G$, what does the resulting problem look like? Does this help think about your question in a different way? I think it means we're given a graph $G^*$ with colors on the vertices and we want to find a vertex cover $G^*$, such that no pair of adjacent selected vertices have the same color. Does that help? $\endgroup$ – D.W. Aug 27 '15 at 18:43
  • $\begingroup$ @D.W. Do you mean instead that we want to find a vertex cover such that no pair of adjacent vertices are of different colors? (since I don't want edges of different colors incident in the original edge cover). Still I see your main idea: A suitable vertex cover of $G^*$ would yield a solution to my original problem. Do you know if this modified VC problem has been studied before? $\endgroup$ – Ari Aug 27 '15 at 21:14

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.