Bodlaender and Fomin prove that an equitable k-coloring can be found in polynomial time on graphs of bounded treewidth. It follows that an l-bounded k-coloring also has a polynomial solution on graphs of bounded treewidth.

The proof is based on the recent Kostochka-Nakprasit-Pemmaraju result concerning the equitable colorability of degenerate graphs. The result is used to determine the point at which the problem is easily found and where a solution in polynomial time can be established by the dynamic programming approach developed by the authors in the paper. The authors also show that the presented approach cannot be used to solve the precolored equitable k-coloring problem by proving that this problem is nondeterministic polynomial time (NP)-complete on trees.