Weighted triangle-free subcubic bisection conjecture
Weighted triangle-free subcubic bisection conjecture
Let be a weighted triangle-free subcubic graph, meaning that has no triangle and maximum degree at most , with non-negative edge weights and total edge weight . A bisection is a cut whose two parts differ in size by at most .
Triangle-free subcubic bisection conjecture. Every weighted triangle-free subcubic graph other than has a bisection of weight at least
The paper proves a lower bound of for graphs other than and notes that the Petersen graph may make optimal; the conjectured improvement remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Stefanie Gerke, Gregory Gutin, Anders Yeo and Yacong Zhou, “Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees”, arXiv:2401.10074 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.