**On **NP**-completeness of
the Problem of Existence of Locally-balanced 2-partition for Bipartite
Graphs **G

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 V_{1} and
V_{2}, which satisfies the condition | |l(v) Ç V_{1}| - |l(v) Ç V_{1}| | £
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.