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) = 4 under the Extended Definition of the Neighbourhood
of a Vertex

   For bipartite graphs G with D(G) = 4 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) V1| | 1 for all vertices of G, where l(v) is the set of all vertices of G the distance of which from v does not exceed 1.