The monotonicity property of M-partition problems

Given a symmetric m×m matrix M with entries from the set {0,1,∗}, the M-partition problem asks whether the vertices of a given graph G can be partitioned into parts V1,V2⋯Vm such that any two distinct vertices u∈Vi and v∈Vj (i,j∈{1,2,…,m}) are adjacent if M(i,j)=1 and non-adjacent if M(i,j)=0. We address a question in Hell (2014) regarding the monotonicity property of M-partition problems, i.e., whether the M-partition problem being NP-complete implies that the M′-partition problem is also NP-complete for any matrix M′ containing M as a principal submatrix and having no ∗ on its main diagonal. We provide a negative answer to this question by providing a class of counter examples. We then introduce some special cases in which the monotonicity property holds.