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 $v\in V(G)$, $\left\vert \vert \{u\in N_{G}(v)\colon\,f(u)=0\}\vert - \vert \{u\in N_{G}(v)\colon\,f(u)=1\}\vert \right\vert≤ 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 \pmod{4}$. Next, we prove that if $G$ is a subcubic bipartite graph that has no cycle of length $2 \pmod{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.
Keywords: locally-balanced 2-partition; NP-completeness; bipartite graph; biregular bipartite graph; subcubic bipartite graph