中文摘要：

给定无向简单图G=（V，E）与颜色集C，并且对C中的每一种颜色。设定一个费用值w（c）∈R^＊．全染色是给出图的一个可行染色使得相关联的边和点、相邻的点或边都染不同的颜色．定义了费用全染色问题，即求解最优的全染色f，使得染色费用和x∈v（c）JE（G）w（f（x））最小，时于树图T，给出了一个2-近似算法，该算法的运行时间为O（nΔ^2）．

英文摘要：

Let G be a simple graph, C be a set of colors, and let w be a cost function which assigns a real number w（c） to each color c in C. A total-coloring of a graph G is to color all the elements of V（G） U E（G） in such a way that no two adjacent or incident elements receive the same color. A 2-approximate algorithm is given to find an optimal cost total-coloring of a given tree T, that is, a total-coloring f of T such that the sum of costs w（f（x）） of colorsf（x） assigned to all elements x is minimum among all total-colorings of T. The algorithm takes time O（ nΔ^2 ） if n is the number of vertices and Δ is the maximum degree of T.