NP-completeness results for partitioning a graph into total dominating sets

A emph{total domatic $k$-partition} of a graph is a partition of its vertex set into $k$ subsets such that each intersects the open neighborhood of each vertex. The maximum $k$ for which a total domatic $k$-partition exists is known as the emph{total domatic number} of a graph $G$, denoted by $d_t(G)$. We extend considerably the known hardness results by showing it is $NP$-complete to decide whether $d_t(G) geq 3$ where $G$ is a bipartite planar graph of bounded maximum degree. Similarly, for every $k geq 3$, it is $NP$-complete to decide whether $d_t(G) geq k$, where $G$ is a split graph or $k$-regular. In particular, these results complement recent combinatorial results regarding $d_t(G)$ on some of these graph classes by showing that the known results are, in a sense, best possible. Finally, for general $n$-vertex graphs, we show the problem is solvable in $2^n n^{O(1)}$ time, and derive even faster algorithms for special graph classes.