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 l-bounded, when each color class has size at most l. We consider the problems to determine for a given graph G (and a given integer l) whether G has an equitable (l-bounded) k-cokoring. 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.
展开▼
