A Note on the Complexity of the Total Domatic Partition Problem in Graphs

Abstract

In this paper, we study the total domatic partition problem for bipartite graphs, split graphs, and graphs with balanced adjacency matrices. We show that the total domatic partition problem is NP-complete for bipartite graphs and split graphs, and show that the total domatic partition problem is polynomial-time solvable for graphs with balanced adjacency matrices. Furthermore, we show that the total domatic partition problem is linear-time solvable for any chordal bipartite graph $G$ if a $\mathrm{\Gamma }$-free form of the adjacency matrix of $G$ is given.