On locally-balanced 2-partitions of bipartite graphs

A. H. Gharibyan ; P. A. Petrosyan

Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 54 (2020) no. 3, pp. 137-145

Résumé

A $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 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 $(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 (\mathrm{mod}~4)$. Next, we prove that if $G$ is a subcubic bipartite graph that has no cycle of length $2 (\mathrm{mod}~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.

Détail

Keywords: locally-balanced $2$-partition, NP-completeness, biregular bipartite graph, subcubic bipartite graph.
Mots-clés : bipartite graph