We have found some necessary conditions for testing the domatic fullness of the permutation graphs. Whenever , G is not domatically full. The permutation graph is regular of degree . But here . Hence this is a kind of permutation graph which can never be domatically full.
Clique criterion Let be a permutation graph in which the vertices have .
In other words, G has p minimum degree vertices. We construct a graph as follows. Let and there exists an edge , if demand to be in different domatic partitions. This implies that for any , forms a clique in . A clique in implies that vertices of G demand to be in different partitions.