Gomes, Guilherme de C. M. and Lima, Carlos V. G. C. and Santos, Vinícius F. dos - Parameterized Complexity of Equitable Coloring

dmtcs:4948 - Discrete Mathematics & Theoretical Computer Science, May 16, 2019, vol. 21 no. 1, ICGT 2018
Parameterized Complexity of Equitable Coloring

Authors: Gomes, Guilherme de C. M. and Lima, Carlos V. G. C. and Santos, Vinícius F. dos

A graph on $n$ vertices is equitably $k$-colorable if it is $k$-colorable and every color is used either $\left\lfloor n/k \right\rfloor$ or $\left\lceil n/k \right\rceil$ times. Such a problem appears to be considerably harder than vertex coloring, being $\mathsf{NP\text{-}Complete}$ even for cographs and interval graphs. In this work, we prove that it is $\mathsf{W[1]\text{-}Hard}$ for block graphs and for disjoint union of split graphs when parameterized by the number of colors; and $\mathsf{W[1]\text{-}Hard}$ 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 \textsc{equitable coloring} is $\mathsf{FPT}$ when parameterized by the treewidth of the complement graph.


Source : oai:arXiv.org:1810.13036
Volume: vol. 21 no. 1, ICGT 2018
Published on: May 16, 2019
Submitted on: November 1, 2018
Keywords: Computer Science - Discrete Mathematics


Share