WorksMathematics
Weighted bisections of triangle-free subcubic graphs
Abstract
We prove a conjecture of Gerke, Gutin, Yeo, and Zhou: for every finite triangle-free subcubic graph other than the claw and every nonnegative edge weighting, there is a bisection whose weight is at least of the total edge weight. This bound is best possible, as shown by the Petersen graph. The proof uses matching-based local distributions, weighted induction, and convex separation to establish the edgewise cut guarantees while maintaining global balance.