Tight bounds on the complexity of semi-equitable coloring of cubic and subcubic graphs

A k-coloring of a graph G=(V,E) is called semi-equitable if there exists a partition of its vertex set into independent subsets V1,…,Vk in such a way that |V1|⁄∈{⌈|V|∕k⌉,⌊|V|∕k⌋} and ‖Vi|−|Vj‖≤1 for each i,j=2,…,k. The color class V1 is called non-equitable. In this note we consider the complexity of semi-equitable k-coloring, k≥4, of the vertices of a cubic or subcubic graph G. In particular, we show that, given a n-vertex subcubic graph G and constants ϵ>0, k≥4, it is NP-complete to obtain a semi-equitable k-coloring of G whose non-equitable color class is of size s if s≥n∕3+ϵn, and it is polynomially solvable if s≤n∕3.