Weighted Berge–Fulkerson matching conjecture for bridgeless cubic graphs
Weighted Berge–Fulkerson matching conjecture for bridgeless cubic graphs
Let be a weighted bridgeless cubic graph, meaning that has no bridges, every vertex has degree , and its edges have non-negative weights. Let be the total edge weight and let be a perfect matching, a set of pairwise disjoint edges meeting every vertex exactly once.
Weighted perfect-matching conjecture. There exists a perfect matching such that
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
Sign in to submit a solution.
No solutions have been posted yet.