Total colorings of degenerate graphs (Q2460621)

Given a simple graph \(G\) of order \(n\) and maximum degree \(\Delta\), a total coloring of \(G\) is a coloring of all elements (vertices and edges) of \(G\) such that no two adjacent or incident elements obtain the same color. A graph \(G\) is called \(s\)-degenerate for an integer \(s\geq 1\) if \(G\) can be reduced to a trivial graph by successive removal of vertices of degree \(\leq s\). The authors prove that the total chromatic number \(\chi"(G)\) of an \(s\)-degenerate graph \(G\) is equal to the trivial lower bound \(\Delta+1\) if \(\Delta \geq 4s+3\). The proof yields an efficient algorithm to find a total coloring of \(G\) with \(\Delta+1\) colors in time \(O(sn^2)\) if \(\Delta\geq 4s+3\). Moreover, it is proved that for partial \(k\)-trees with bounded \(k\) a total coloring with \(\Delta+1\) colors can be found in linear time.