Coloring Weighted 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 [[??].sub.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 uv. 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. Povzetek: Opisano je barvanje grafov.