# Path coloring in general graphs

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?

-
What is the definition of path coloring? Also, would you please provide more info (a link very be especially appreciated) about Raghavan and Upfal's algorithm? –  Yixin Cao Nov 9 '12 at 17:18
The first problem in Wikipedia entry: en.wikipedia.org/wiki/Path_coloring –  Arindam Pal Nov 9 '12 at 17:51
It would be even more helpful to make the definition inline. –  Suresh Venkat Nov 9 '12 at 18:23
Added the definition as well as the reference to Raghavan and Upfal paper. –  Arindam Pal Nov 10 '12 at 2:11

Edit: In the end I did find a reference for the reduction I remembered. It is given in Edge intersection graphs of single bend paths on a grid by Golumbic, Lipshteyn, and Stern. So, to sum up, the class of graphs obtained as intersections of paths on a grid contains all graphs. Therefore, path coloring on grids is as hard to approximate as graph coloring ($n^{1-\epsilon}$-hard).
We start with a graph $G(V,E)$ on $n$ vertices and the question is if it can be colored with $k$ colors. Construct a graph $H$ which is a $n\times ({n\choose 2}+1)$ grid (we index the rows by the vertices of $G$ and the columns by pairs of vertices of $G$). We will add one path in this graph for each vertex of $G$. Initially, each of these paths is simply a row of the grid, so no two of them intersect and they all have length $n\choose 2$. The idea here is that we will use the $n\choose 2$ edges between columns of the grid to simulate the edges of the original graph. For example, if vertex $i$ is connected to vertex $j$ in $G$, with $i<j$, take the path that runs through row $i$ and re-route it as follows: the path now goes from vertex $(i,(i,j))$ to $(j,(i,j))$, then it uses the next edge on the $j$-th row and then it goes back to row $i$. This creates an intersection between paths $i$ and $j$, but no other edge intersections. By adding the rest of the edges of $G$ this way, the resulting instance is $k$-colorable iff $G$ is.