We discuss the Precoloring Extension (PrExt) and the
List Coloring (LiCol) problems for trees, partial
k-trees and cographs in the decision and the
construction versions. Both problems for partial
k-trees are solved in linear time, when the number of
colors is bounded by a constant and by
O(|V|k+2)-algorithms in general. For trees, we
improve this to linear time. In contrast to that, PrExt
and LiCol differ in complexity for cographs. While the
first has a linear decision algorithm, the second is
shown to be NP-complete. We give polynomial time
algorithms for the corresponding enumeration problems
#PrExt and #LiCol on partial k-trees and trees and for
#PrExt on cographs.
