Geodesic
Parameterized Complexity of Equitable Coloring
Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2019_21_1_a4,
     author = {Gomes, Guilherme de C. M. and Lima, Carlos V. G. C. and Santos, Vin{\'\i}cius F. dos},
     title = {Parameterized {Complexity} of {Equitable} {Coloring}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {21},
     number = {1},
     year = {2019},
     doi = {10.23638/DMTCS-21-1-8},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-8/}
}
TY  - JOUR
AU  - Gomes, Guilherme de C. M.
AU  - Lima, Carlos V. G. C.
AU  - Santos, Vinícius F. dos
TI  - Parameterized Complexity of Equitable Coloring
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-8/
DO  - 10.23638/DMTCS-21-1-8
LA  - en
ID  - DMTCS_2019_21_1_a4
ER  - 
%0 Journal Article
%A Gomes, Guilherme de C. M.
%A Lima, Carlos V. G. C.
%A Santos, Vinícius F. dos
%T Parameterized Complexity of Equitable Coloring
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-8/
%R 10.23638/DMTCS-21-1-8
%G en
%F DMTCS_2019_21_1_a4
Gomes, Guilherme de C. M.; Lima, Carlos V. G. C.; Santos, Vinícius F. dos. Parameterized Complexity of Equitable Coloring. Discrete mathematics & theoretical computer science, ICGT 2018, Tome 21 (2019) no. 1. doi : 10.23638/DMTCS-21-1-8. http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-1-8/

Cité par Sources :