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.