Parameterized Complexity of Equitable Coloring
share
A graph on n vertices is equitably k-colorable if it is k-colorable and every color is used either n/k or n/k times. Such a problem appears to be considerably harder than vertex coloring, being NP-Complete even for cographs and interval graphs. In this work, we prove that it is W[1]-Hard for block graphs and for disjoint union of split graphs when parameterized by the number of colors; and W[1]-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 equitable coloring is FPT when parameterized by the treewidth of the complement graph.
READ FULL TEXT