Weighted Berge–Fulkerson matching conjecture for bridgeless cubic graphs

From papers

Let GG be a weighted bridgeless cubic graph, meaning that GG has no bridges, every vertex has degree 33, and its edges have non-negative weights. Let w(G)w(G) be the total edge weight and let MM be a perfect matching, a set of pairwise disjoint edges meeting every vertex exactly once.

Weighted perfect-matching conjecture. There exists a perfect matching MM such that

w(M)w(G)3.w(M)\geq \frac{w(G)}{3}.

This is presented as a weighted consequence of the Berge–Fulkerson conjecture and would imply the relevant case of the paper's triangle-free cubic bisection conjecture. Its general validity 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.