We show that a class of vertex partitioning problems that can be expressed in monadic second order logic (MSOL) are polynomials on graphs of bounded clique-width. This class includes coloring, H-free coloring, domatic number and partition into perfect graphs. Moreover we show that a class of vertex and edge partitioning problems are polynomials on graphs of bounded treewidth.