S.V. Balikyan, R.R. Kamalian

On NP-completeness of the Problem of Existence of Locally-balanced 2-partition for
Bipartite Graphs
G with D(G) = 3

   For bipartite graphs G with D(G) = 3 the NP-completeness is shown for the problem of such partition of the set of vertices of G in two sets V1 and V2,which satisfies the condition ||l(v)V1| - |l(v)V2|| 1 for all vertices of G, where l(v) is the set of adjacent vertices of v.