Tight Bounds on the Complexity of Semi-Equitable Coloring of Cubic and Subcubic Graphs

H. Furmańczyk, M. Kubale

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 $V_1,\dots ,V_k$ in such a way that $|V_1| \noti…