Parameterized Complexity of Equitable Coloring

A graph on $n$ vertices is equitably $k$-colorable if it is $k$-colorable and every color is used either $\lfloor n\mathrm{/}k\rfloor$ or $\left\lceil n/k \right\rceil$ times. Such a problem appears to be considerably harder than vertex coloring, being $\mathsf{N}\mathsf{P}\text{-}\mathsf{C}\mathsf{o}\mathsf{m}\mathsf{p}\mathsf{l}\mathsf{e}\mathsf{t}\mathsf{e}$ even for cographs and interval graphs. In this work, we prove that it is $\mathsf{W}[\mathsf{1}]\text{-}\mathsf{H}\mathsf{a}\mathsf{r}\mathsf{d}$ for block graphs and for disjoint union of split graphs when parameterized by the number of colors; and $\mathsf{W}[\mathsf{1}]\text{-}\mathsf{H}\mathsf{a}\mathsf{r}\mathsf{d}$ for $K_{1,4}$-free interval graphs when parameterized by treewidth, number of colors and maximum degree, generalizing a result by Fellows et al. (2014) through a much simpler reduction. Using a previous result due to Dominique de Werra (1985), we establish a dichotomy for the complexity of equitable coloring of chordal graphs based on the size of the largest induced star. Finally, we show that $\text{textsc}equitablecoloring$ is $\mathsf{F}\mathsf{P}\mathsf{T}$ when parameterized by the treewidth of the complement graph.