Defective Coloring on Classes of Perfect Graphs

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 maximumdegree induced by any color class is at most $\Delta^*$. We show that thisnatural generalization of Coloring is much harder on several basic graphclasses. In particular, we show that it is NP-hard on split graphs, even whenone of the two parameters $\chi_d$, $\Delta^*$ is set to the smallest possiblefixed value that does not trivialize the problem ($\chi_d = 2$ or $\Delta^* =1$). Together with a simple treewidth-based DP algorithm this completelydetermines the complexity of the problem also on chordal graphs. We thenconsider the case of cographs and show that, somewhat surprisingly, DefectiveColoring turns out to be one of the few natural problems which are NP-hard onthis class. We complement this negative result by showing that DefectiveColoring is in P for cographs if either $\chi_d$ or $\Delta^*$ is fixed; thatit is in P for trivially perfect graphs; and that it admits a sub-exponentialtime algorithm for cographs when both $\chi_d$ and $\Delta^*$ are unbounded