Abstract
The domatic number of a graph G = (V,E), denoted by DN(G), is the maximum number k such that V can be partitioned into k disjoint dominating sets. The domatic number problem is to find DN(G) for a graph G. The domatic partition problem is to find a partition of the vertices of G into DN(G) disjoint dominating sets. The k-domatic partition problem with fixed k is to find a partition of the vertices of G into k disjoint dominating sets. The unique domatic partition problem is to decide whether G has an unique domatic partition or not. The unique k-domatic partition problem with fixed k is to decide whether G has an unique k-domatic partition or not. In this thesis, we show that 3-domatic partition problem is NP-complete on planar graphs and planar-bipartite graphs and the domatic partition problem is NP-complete on co-bipartite graphs. We also showed that the unique 3-domatic partition problem is NP-hard on general graphs. Moreover, we propose a 3-domatic partition algorithm for maximal planar graphs in O(n) time and O(n^3)-time algorithms for the domatic partition problem on P4-sparse graphs and tree-cographs, respectively.