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

A 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 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) >= 3 where G is a bipartite planar graph of bounded maximum degree. Similarly, for every k >= 3, it is NP-complete to decide whether d(t) (G) >= k, where G is split 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. (C) 2018 Elsevier B.V. All rights reserved.