ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS - Gharibyan, Aram H.; Petrosyan, Petros A. (Proceedings of the YSU A: Physical and Mathematical Sciences, 2020)
A 2-partition of a graph G is a function f:V(G)→ {0,1}. A 2-partition f of a graph G is a locally-balanced with an open neighborhood, if for every vV(G), {uN_G(v)f(u)=0}- {uN_G(v)f(u)=1}≤ 1. A bipartite graph is (a,b)-biregular if all vertices in one part have degree a and all vertices in the other part have degree b. In this paper we prove that the problem of deciding, if a given graph has a locally-balanced 2-partition with an open neighborhood is NP-complete even for (3,8)-biregular bipartite graphs. We also prove that a (2,2k+1)-biregular bipartite graph has a locally-balanced 2-partition with an open neighbourhood if and only if it has no cycle of length 2 4. Next, we prove that if G is a subcubic bipartite graph that has no cycle of length 2 4, then G has a locally-balanced 2-partition with an open neighbourhood. Finally, we show that all doubly convex bipartite graphs have a locally-balanced 2-partition with an open neighbourhood.