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 $2$-partition $f^{ \prime}$ of a graph $G$ is a \emph{ locally-balanced with a closed neighborhood} if for every $v\in V(G)$, $$\left\vert \vert \{ u\in N_{ G}[v]\colon\,f^{ \prime}(u)=0\}\vert - \vert \{ u\in N_{ G}[v]\colon\,f^{ \prime}(u)=1\}\vert \right\vert\leq 1.$$ In this paper we prove that the problem of the existence of locally-balanced $2$-partition with an open (closed) neighborhood is $NP$-complete for some restricted classes of graphs. In particular, we show that the problem of deciding if a given graph has a locally-balanced $2$-partition with an open neighborhood is $NP$-complete for biregular bipartite graphs and even bipartite graphs with maximum degree $4$, and the problem of deciding if a given graph has a locally-balanced $2$-partition with a closed neighborhood is $NP$-complete even for subcubic bipartite graphs and odd graphs with maximum degree $3$. Last results prove a conjecture of Balikyan and Kamalian.
Categories: math.CO