Cooperative graph coloring
let G(V,E) be a graph where the edges are colored by three colors (1,2,3). for each color i, the set of edges that are colored by i, create a path (or more generally disjoint union of paths).
I need to find a coloring with the 3 colors for the vertices such that if u,v are colored with color i, then there is no edge with color i between them.
I think there should be some simple solution here, but all I tried so far didn't work. I thought about using induction, by taking out a vertex with degree one from edges with color i, and then try to color the rest of the graph, or dropping an edge, and other similar ideas. the problem is that the new graph has constraints about the color of some of the vertices and is not the same as the original problem.