Geodesic
Defective Coloring on Classes of Perfect Graphs
Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1.

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

In Defective Coloring we are given a graph $G$ and two integers $\chi_d$, $\Delta^*$ and are asked if we can $\chi_d$-color $G$ so that the maximum degree induced by any color class is at most $\Delta^*$. We show that this natural generalization of Coloring is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters $\chi_d$, $\Delta^*$ is set to the smallest possible fixed value that does not trivialize the problem ($\chi_d = 2$ or $\Delta^* = 1$). Together with a simple treewidth-based DP algorithm this completely determines the complexity of the problem also on chordal graphs. We then consider the case of cographs and show that, somewhat surprisingly, Defective Coloring turns out to be one of the few natural problems which are NP-hard on this class. We complement this negative result by showing that Defective Coloring is in P for cographs if either $\chi_d$ or $\Delta^*$ is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both $\chi_d$ and $\Delta^*$ are unbounded.
DOI : 10.46298/dmtcs.4926
Classification : 05C15, 05C17, 05C75 
@article{DMTCS_2022_24_1_a0,
     author = {Belmonte, R\'emy and Lampis, Michael and Mitsou, Valia},
     title = {Defective {Coloring} on {Classes} of {Perfect} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2022},
     doi = {10.46298/dmtcs.4926},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.4926/}
}
TY  - JOUR
AU  - Belmonte, Rémy
AU  - Lampis, Michael
AU  - Mitsou, Valia
TI  - Defective Coloring on Classes of Perfect Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2022
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.4926/
DO  - 10.46298/dmtcs.4926
LA  - en
ID  - DMTCS_2022_24_1_a0
ER  - 
%0 Journal Article
%A Belmonte, Rémy
%A Lampis, Michael
%A Mitsou, Valia
%T Defective Coloring on Classes of Perfect Graphs
%J Discrete mathematics & theoretical computer science
%D 2022
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.4926/
%R 10.46298/dmtcs.4926
%G en
%F DMTCS_2022_24_1_a0
Belmonte, Rémy; Lampis, Michael; Mitsou, Valia. Defective Coloring on Classes of Perfect Graphs. Discrete mathematics & theoretical computer science, Tome 24 (2022) no. 1. doi : 10.46298/dmtcs.4926. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.4926/

Cité par Sources :