# On hardness of finding total dominating sets in triangle-free graphs

A total dominating set $$S\subset V(G)$$ is a set of vertices such that $$\forall v\in V(G)$$, $$v$$ has a neighbour in $$S$$. The minimum total dominating set of $$G$$ is a total dominating set of $$G$$ of minimum possible size. The minimum total domination number of $$G$$ is represented by $$\gamma_t(G)$$.It is known that MTDS is $$NP-complete$$ for general graphs, bipartite graphs, chordal graphs, etc. [REFERENCE: Henning, Michael A.. “A survey of selected recent results on total domination in graphs.” Discret. Math. 309 (2009): 32-63.]

Do we know anything about hardness of MTDS on triangle-free graphs of bounded degree?Or triangle-free graphs in general? ( A graph is triangle-free if any three vertices does not form a triangle).

• All bipartites are triangle free. That answers your second question. Jul 3, 2023 at 9:23
• Yes that's correct. Jul 3, 2023 at 9:32
• It would be good if you could tell the motivation for studying this version since there could be many such variants. Jul 3, 2023 at 10:05
• So I am studying this specific kind of proper coloring of graphs called "cd-coloring" in which every color class is dominated by atleast one vertex. The cd-chromatic number is denoted by $\chi_{cd}$. So it is proven that for triangle -free graphs $G$ ,$\chi_{cd}(G)=\gamma_t(G)$. Right now my motive is to study cd-colorability in regular graphs(in particular cubic graphs). I want to prove this is $NP-hard$ for triangle-free cubic graphs. So I tried to reduce *total domination in cubic graphs*(which is $NP-complete$) to cd -colorability in cubic graphs, but till now am not successful. Jul 3, 2023 at 13:22
• (Continuing) So I am searching for total-domination $NP-completeness$ results for triangle-free graphs of bounded degree, So that I can reduce it to cd-colorability of some triangle-free $k$-regular graphs, thereby proving it $NP-complete$. Jul 3, 2023 at 13:25

The problem is indeed $$\mathsf{NP}$$-hard on bipartite graphs (which are triangle-tree) of degree at most $$3$$. See Theorem 6 of this paper.