Path coloring
In graph theory, path coloring usually refers to one of two problems:
 The problem of coloring a (multi)set of paths  in graph , in such a way that any two paths of  which share an edge in  receive different colors. Set  and graph  are provided at input. This formulation is equivalent to vertex coloring the conflict graph of set , i.e. a graph with vertex set  and edges connecting all pairs of paths of  which are not edge-disjoint with respect to .
 The problem of coloring (in accordance with the above definition) any chosen (multi)set  of paths in , such that the set of pairs of end-vertices of paths from  is equal to some set or multiset , called a set of requests. Set  and graph  are provided at input. This problem is a special case of a more general class of graph routing problems, known as call scheduling.
In both the above problems, the goal is usually to minimise the number of colors used in the coloring. In different variants of path coloring,  may be a simple graph, digraph or multigraph.

References
The Complexity of Path Coloring and Call Scheduling by Thomas Erlebach and Klaus Jansen
A compendium of NP optimization problems by Viggo Kann (problem: Minimum Path Coloring)

Graph coloring