A linear algorithm for finding total colorings of partial \(k\)-trees (Q4511238)

A total coloring of a graph \(G=(V,E)\) is an assignment of colors to all vertices and edges of \(G\), such that no two adjacent or incident elements have the same color. In this paper, the problem of finding a total coloring of a partial \(k\)-tree with a minimum number of colors is addressed. Partial \(k\)-trees are also known as graphs of treewidth at most \(k\). In an earlier paper [Lect. Notes Comput. Sci. 1517, 100-113 (1998; Zbl 0915.05059)] the authors gave a polynomial algorithm for this problem, but with a high time complexity. In this paper, the authors improve upon the result and give a linear time algorithm. If the maximum degree of the partial \(k\)-tree \(G\) is bounded, then a dynamic programming algorithm can solve the problem optimally in linear time. The paper shows that if the maximum degree \(d\) of \(G\) is at least \(8k^2\), then the total coloring number of \(G\) is exactly \(d+1\), and a total coloring with \(d+1\) colors can be constructed in linear time. For the entire collection see [Zbl 0933.00045].