Sharp Bounds for the Complexity of Semi-Equitable Coloring of Cubic and Subcubic Graphs

H. Furmańczyk, M. Kubale

Published 2016-06-20Version 1

In this note we consider the complexity of semi-equitable $k$-coloring, $k\geq 4$, of the vertices of a cubic or subcubic graph $G$. In particular, we show that, given $n$-vertex subcubic graph $G$ and $k \geq 4$, a semi-equitable $k$-coloring of $G$ is NP-hard if $s \geq 7n/20$, and polynomially solvable if $s \leq 7n/21$, where $s$ is the size of maximum color class of the coloring.