ColoringWeighted Series-Parallel Graphs

Let G be a series-parallel graph with integer edge weights. A p-coloring of G is a mapping of vertices of G into Z(p) (ring of integers modulo p) so that the distance between colors of adjacent vertices u and v is at least the weight of the edge u v. We describe a quadratic time p-coloring algorithm where p is either twice the maximum edge weight or the largest possible sum of three weights of edges lying on a common cycle.