A class domination coloring (also called as cd-coloring) of a graph is a proper coloring such that for every color class, there is a vertex that dominates it. The minimum number of colors required for a cd-coloring of the graph G, denoted by X_(cd)(G), is called the class domination chromatic number (cd-chromatic number) of G. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph G on n vertices, find its cd-chromatic number. (2) Given a graph G and integers k and q, can we delete at most k vertices such that the cd-chromatic number of the resulting graph is at most ql For the first problem, we give an exact algorithm with running time O(2~n~4 log n). Also, we show that the problem is FPT with respect to the number of colors q as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with O(q~3) vertices. For the second (deletion) problem, we show NP-hardness for each q ≥ 2. Further, on split graphs, we show that the problem is NP-hard if q is a part of the input and FPT with respect to k and q. As recognizing graphs with cd-chromatic number at most q is NP-hard in general for q ≥ 4, the deletion problem is unlikely to be FPT when parameterized by the size of deletion set on general graphs. We show fixed parameter tractability for q ∈ {2,3} using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines.
展开▼
