Let G be a graph, and let each vertex v of G have a positive integer weight ω(v). A multicoloring of G is to assign each vertex v a set of ω(v) colors so that any pair of adjacent vertices receive disjoint sets of colors. This paper presents an algorithm to find a multicoloring of a given series-parallel graph G with the minimum number of colors in time O(n W), where n is the number of vertices and W is the maximum weight of vertices in G.
- Dynamic programming algorithm
- Series-parallel graph