  A code design problem for memory devises with restricted state transitions is
formulated as a combinatorial optimization problem that is called a subgraph
domatic partition (subDP) problem. If any neighbor set of a given state
transition graph contains all the colors, then the coloring is said to be
valid. The goal of a subDP problem is to find a valid coloring with the largest
number of colors for a subgraph of a given directed graph. The number of colors
in an optimal valid coloring gives the writing capacity of a given state
transition graph. The subDP problems are computationally hard; it is proved to
be NP-complete in this paper. One of our main contributions in this paper is to
show the asymptotic behavior of the writing capacity $C(G)$ for sequences of
dense bidirectional graphs, that is given by C(G)=Omega(n/ln n) where n is the
number of nodes. A probabilistic method called Lovasz local lemma (LLL) plays
an essential role to derive the asymptotic expression.
