Paperlane

no. 16 · Tuesday 17 November 2026

Weighted bisections of triangle-free subcubic graphs

Shufei Wu and Qinghou Zeng

math.CO

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 $11/15$ 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.

fields
Combinatorics
pdf ↗ page arXiv:2611.19881 ↗