Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors.We know that coloring a set of paths with the minimum number of colors is in $\sf{P}$, if the underlying graph is also a path. It is known that path coloring in trees is $\sf{NP}$-hard. There is a greedy algorithm by Raghavan and Upfal (Efficient routing in all-optical networks,  STOC 1994), which colors any set of paths of load $L$ on an undirected tree using at most $3L/2$ colors. This bound is tight, since there exists a set of undirected paths on an undirected binary tree, which requires at least $3L/2$ colors.What are the results known for general graphs, both approximation algorithms and lower bounds?
Path coloring in general graphs
cc.complexity theory;ds.algorithms;graph theory;approximation algorithms;graph colouring