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?