Equitable colorings of bounded treewidth graphs

A proper coloring of a graph G is equitable if the sizes of any two color classes differ by at most one. A proper coloring is ℓ-bounded, when each color class has size at most ℓ. We consider the problems to determine for a given graph G (and a given integer ℓ) whether G has an equitable (ℓ-bounded) k-coloring. We prove that both problems can be solved in polynomial time on graphs of bounded treewidth, and show that a precolored version remains NP-complete on trees.