The spanning-tree bound conjecture for weighted triangle-free graphs

About 5 years old · traced to

Let GG be a weighted triangle-free graph, and let TT be a spanning tree of GG. Spanning-tree bound conjecture. One should have

mac⁡(G)≥w(G)2+3w(T)8.\operatorname{mac}(G)\geq \frac{w(G)}{2}+\frac{3w(T)}{8}.

The conjecture would determine the optimal value of the spanning-tree parameter for triangle-free graphs, improving the established lower bound 1/4≤θ≤3/81/4\leq\theta\leq3/8 to θ=3/8\theta=3/8.

References

Primary source

Gregory Gutin and Anders Yeo, “Lower Bounds for Maximum Weighted Cut”, arXiv:2104.05536 (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.