Delphi.science

Weighted bisections of triangle-free subcubic graphs

Source: arxiv.org/abs/2611.19881

Shufei Wu, Qinghou Zeng

arXivarxiv/2611.19881Nov 15, 2026math.COscore 0

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.

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

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}'