ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS

A2-partition of a graphGis a functionf:V(G)→{0,1}. A2-partitionfofa graphGis alocally-balanced with an open neighborhood, if for everyv∈V(G),||{u∈NG(v):f(u) =0}|−|{u∈NG(v):f(u) =1}||≤1. A bipartite graph is(a,b)-biregularif all vertices in one part have degreeaand all vertices in theother part have degreeb. In this paper we prove that the problem of deciding,if a given graph has a locally-balanced2-partition with an open neighborhoodisNP-complete even for(3,8)-biregular bipartite graphs. We also prove that a(2,2k+1)-biregular bipartite graph has a locally-balanced2-partition with anopen neighbourhood if and only if it has no cycle of length2(mod 4). Next,we prove that ifGis a subcubic bipartite graph that has no cycle of length2(mod 4), thenGhas a locally-balanced2-partition with an open neighbourhood.Finally, we show that all doubly convex bipartite graphs have a locally-balanced2-partition with an open neighbourhood.