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

dmtcs:4948 - Discrete Mathematics & Theoretical Computer Science, May 16, 2019, vol. 21 no. 1, ICGT 2018 - https://doi.org/10.23638/DMTCS-21-1-8
Parameterized Complexity of Equitable ColoringArticle

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

    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 K1,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 FPT when parameterized by the treewidth of the complement graph.


    Volume: vol. 21 no. 1, ICGT 2018
    Published on: May 16, 2019
    Accepted on: May 4, 2019
    Submitted on: November 1, 2018
    Keywords: Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 907 times.
    This article's PDF has been downloaded 451 times.