Weighted bisections of triangle-free subcubic graphs
Source: arxiv.org/abs/2611.19881
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.19881
curl -X POST /api/v1/records/arxiv/2611.19881/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.19881/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'