Total Domination, Separated-Cluster, CD-Coloring: Algorithms and Hardness

Domination and coloring are two classic problems in graph theory. In this paper, our major focus is on the CD-coloring problem, which incorporates the flavors of both domination and coloring in it. Let G be an undirected graph. A proper vertex coloring of G is said to be a cd-coloring, if each color class has a dominating vertex in G. The minimum integer k for which there exists a cd-coloring of G using k colors is called the cd-chromatic number of G, denoted as \({{\chi }_{cd}}(G)\) . A set \(S\subseteq V(G)\) is said to be a total dominating set, if any vertex in G has a neighbor in S. The total domination number of G, denoted as \(\gamma \) \(_t(G)\) , is defined to be the minimum integer k such that G has a total dominating set of size k. A set \(S\subseteq V(G)\) is said to be a separated-cluster (also known as sub-clique) if no two vertices in S lie at a distance exactly 2 in G. The separated-cluster number of G, denoted as \({\omega _{s}}(G)\) , is defined to be the maximum integer k such that G has a separated-cluster of size k. In this paper, we contribute to the literature connecting CD-coloring with the problems, Total Domination and Separated-Cluster. For any graph G, we have \({{\chi }_{cd}}(G)\ge \gamma _t(G)\) and \({{\chi }_{cd}}(G)\ge {\omega _{s}}(G)\) . First, we explore the connection of CD-Coloring problem to the well-known problem Total Domination. Note that Total Domination is known to be NP-Complete for triangle-free 3-regular graphs. We generalize this result by proving that both the problems CD-Coloring and Total Domination are NP-Complete, and do not admit any subexponential-time algorithms on triangle-free d-regular graphs, for each fixed integer \(d\ge 3\) , assuming the Exponential Time Hypothesis. We also study the relationship between the parameters \({{\chi }_{cd}}(G)\) and \({\omega _{s}}(G)\) . Analogous to the well-known notion of ‘perfectness’, here we introduce the notion of ‘cd-perfectness’. We prove a sufficient condition for a graph G to be cd-perfect (i.e. \({{\chi }_{cd}}(H)= {\omega _{s}}(H)\) , for any induced subgraph H of G). Our sufficient condition is also necessary for certain graph classes (like triangle-free graphs). This unified approach of ‘cd-perfectness’ has several exciting consequences. In particular, it is interesting to note that the same framework can be used as a tool to derive both positive and negative results concerning the algorithmic complexity of CD-coloring and Separated-Cluster.