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.
References
- Stefanie Gerke, Gregory Gutin, Anders Yeo and Yacong Zhou, “Lower Bounds for Maximum Weight Bisections of Graphs with Bounded Degrees”, arXiv:2401.10074 (2024).
Progress summary
Never refreshed
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.