ON LOCALLY-BALANCED 2-PARTITIONS OF BIPARTITE GRAPHS
DOI:
https://doi.org/10.46991/PYSU:A/2020.54.3.137Keywords:
locally-balanced 2-partition, NP-completeness, bipartite graph, biregular bipartite graph, subcubic bipartite graphAbstract
A \emph{$2$-partition of a graph $G$} is a function $f:V(G)\rightarrow \{0,1\}$. A $2$-partition $f$ of a graph $G$ is a \emph{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\leq 1$. A bipartite graph is \emph{$(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.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2020 Proceedings of the YSU
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.