Cost total colorings of trees

A total coloring of a graph G is to color all vertices and edges of G so that no two adjacent or incident elements receive the same color. Let C be a set of colors, and let omega be a cost function which assigns to each color c in C a real number omega(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs omega(f(x)) of colors f(x) assigned to all vertices and edges x is as small as possible. In this paper, we give an algorithm to find an optimal total coloring of any tree T in time O(nDelta(3)) where n is the number of vertices in T and Delta is the maximum degree of T.