Weighted triangle-free subcubic bisection conjecture

From papers

Let G=(V,E,w)G=(V,E,w) be a weighted triangle-free subcubic graph, meaning that GG has no triangle and maximum degree at most 33, with non-negative edge weights and total edge weight w(G)w(G). A bisection is a cut whose two parts differ in size by at most 11.

Triangle-free subcubic bisection conjecture. Every weighted triangle-free subcubic graph other than K1,3K_{1,3} has a bisection of weight at least

1115w(G).\frac{11}{15}w(G).

The paper proves a lower bound of 613855w(G)\frac{613}{855}w(G) for graphs other than K1,3K_{1,3} and notes that the Petersen graph may make 1115\frac{11}{15} 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

No solutions have been posted yet.