Multicolorings of series-parallel graphs
Let G be a graph, and let each vertex v of G have a positive integer weight omega(v). A multicoloring of G is to assign each vertex v a set of omega(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 0(nW), where n is the number of vertices and W is the maximum weight of vertices in G.
multicoloring coloring series-parallel graph dynamic programming algorithm