Bisections of graphs under degree constraints

Partitioning combinatorial objects is of fundamental importance both from theoretical and application perspectives. It is a folklore exercise to show that every \(m\)-edge graph has a maximum cut of size at least \(m/2\), i.e., its vertices can be partitioned into two parts such that at least \(m/2\) edges have their end vertices in different parts. There are many extensions of this result, including the following two. Erdős showed that every graph with minimum degree \(2k-1\) admits a partition such that each vertex has at least \(k\) neighbors in the other part. Stiebitz then complemented this result, resolving a conjecture of Thomassen, by showing that very graph with minimum degree \(2k+1\) admits a partition such that each vertex has at least \(k\) neighbors in its own part.

This paper concerns bisections, i.e., partitions of the vertex set into two parts of equal size, in which the number of neighbors of each vertex \(v\) in one of the parts is constrained by a function of the degree of \(v\). In 2002, Bollobás and Scott conjectured that every graph admits a bisection such that each vertex \(v\) has at least \((\deg(v)-1)/2\) of its neighbors in the other part. The conjecture was disproved, however, the slightly weaker statement that every graph admits a bisection such that each vertex \(v\) has at least \(\deg(v)/2-O(1)\) of its neighbors in the other part remains widely open.

One of the main results of this paper asserts that every graph has a bisection such that each vertex \(v\) has at least \((\deg(v)-o(1))/4\) neighbors in the other part. This is the first result establishing the existence of a bisection in which a constant proportion of the neighbors of each vertex lies in the other part. This statement is complemented by showing that every graph admits a bisection such that each vertex \(v\) has at least \((\deg(v)-o(1))/4\) neighbors in its own part.