  The regular number of a graph G denoted by reg(G) is the minimum number of
subsets into which the edge set of G can be partitioned so that the subgraph
induced by each subset is regular. In this work we answer to the problem posed
as an open problem in A. Ganesan et al. (2012) [3] about the complexity of
determining the regular number of graphs. We show that computation of the
regular number for connected bipartite graphs is NP-hard. Furthermore, we show
that, determining whether reg(G) = 2 for a given connected 3-colorable graph G
is NP-complete. Also, we prove that a new variant of the Monotone Not-All-Equal
3-Sat problem is NP-complete.
