A Linear Algorithm for Finding Total Colorings of Partial $k$-Trees (Algorithm Engineering as a New Paradigm)
Shuji Isobe, Xiao Zhou, Takao Nishizeki · Kyoto University Research Information Repository (Kyoto University) · 1999
A total coloring of a graph $G$ is a coloring of all elements of $G$ , i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color.The total coloring problem is to find a total coloring of a given graph with the minimum number of colors.Many combinatorial problems can be efficiently solved for partial $k$ -trees, i.e., graphs with bounded tree-width.However, no efficient algorithm has been known for the total coloring problem on partial $k$ -trees although a polynomial-time algorithm of very high order has been known.In this paper, we give a linear-time algorithm for the total coloring problem on partial $k$ -trees with bounded $k$ .