Cost Total Colorings of Trees

Shuji ISOBE  Xiao ZHOU  Takao NISHIZEKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D    No.2    pp.337-342
Publication Date: 2004/02/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
Category: 
Keyword: 
cost total coloring,  dynamic programming,  matching,  total coloring,  tree,  

Full Text: PDF>>
Buy this Article


Summary: 
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 ω be a cost function which assigns to each color c in C a real number ω(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs ω(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(nΔ3) where n is the number of vertices in T and Δ is the maximum degree of T.