Weak external bisections of regular graphs (Q6544518)

The article works on classical graph theory. It is devoted to the partial solution of the graph bisection problem. A bipartition of the graph $G$ is a bipartition of the set of vertices $- V(G)$, with $V(G)=V_1\cup V_2$ and $V_1\cap V_2=\emptyset$. If a bipartition satisfies $||V_1|-|V_2||\leq 1$, that is called a bisection of the graph. \textit{B. Bollobás} and \textit{A. D. Scott} [Random Struct. Algorithms 21, No. 3--4, 414--430 (2002; Zbl 1013.05059)] conjectured that each graph admits a bisection such that for every vertex, its external degree is greater than or equal to its internal degree minus one. In this article, the authors confirm this conjecture for some regular graphs. These results (obtained in the article) extend the results obtained by \textit{A. Ban} and \textit{N. Linial} [J. Graph Theory 83, No. 1, 5--18 (2016; Zbl 1346.05223)]. The authors also give an upper bound of the maximum bisection of graphs.