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

Chuan-Min Lee1, Sz-Lin Wu1, Hsin-Lun Chen1, Chia-Wei Chang1, Tai Lee1
1 Department of Computer and Communication Engineering , Ming Chuan University, 5 De Ming Rd., Guishan District, Taoyuan County 333, Taiwan.

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 \( \Gamma \)-free form of the adjacency matrix of \( G \) is given.

Keywords: Graph algorithm; Total domatic partition; Balanced adjacency matrix; Hypergraph.