On Chromatic Transversal Domination in Graphs

Abstract

Let $G=(V,E)$ be a graph with chromatic number $k$. A dominating set $D$ of $G$ is called a chromatic transversal dominating set (ctd-set) if $D$ intersects every color class of any $k$-coloring of $G$. The minimum cardinality of a ctd-set of $G$ is called the chromatic transversal domination number of $G$ and is denoted by ${\gamma }_{ct}(G)$. In this paper, we obtain sharp upper and lower bounds for ${\gamma }_{ct}$ for the Mycielskian $\mu (G)$ and the shadow graph $\text{Sh}(G)$ of any graph $G$. We also prove that for any $c\ge 2$, the decision problem corresponding to ${\gamma }_{ct}$ is NP-hard for graphs with $\chi (G)=c$.