Lower Bounds for Maximum Weight Bisections of Weighted Triangle-Free Subcubic Graphs

A bisection of a graph is a cut in which the number of vertices in the two parts of the cut differ by at most 1. In this paper, we consider maximum weight bisections of edge-weighted triangle-free subcubic graphs and show that every weighted triangle-free subcubic graph (Formula presented.) has a bisection with weight at least (Formula presented.) unless (Formula presented.) (where (Formula presented.)). We conjecture that (Formula presented.) can be replaced by (Formula presented.), the value of (Formula presented.) for the Peterson graph and prove the conjecture for weighted bridgeless triangle-free cubic graphs.