The NP-completeness of the domatic number problem in split graphs shows that they are not domatically full. However, it is not known whether permutation graphs are domatically full. In this paper we derive tighter upper bounds than the existing upper bound of minimum degree plus one, for the domatic number problem for general graphs and split graphs. We also derived a number of necessary conditions for a permutation graph to be not domatically full and prove that the class of permutation graphs are indeed not domatically full. These results lead to simple and fast polynomial-time heuristic algorithms for obtaining a domatic partitioning of split and permutation graphs.
Experimental results demonstrate the near optimality of the heuristic algorithm.