On Chromatic Transversal Domination in Graphs

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 \geq 2 \), the decision problem corresponding to \( \gamma_{ct} \) is NP-hard for graphs with \( \chi(G) = c \).