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.