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

From papers

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.

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

Gregory Gutin and Anders Yeo, “Lower Bounds for Maximum Weighted Cut”, arXiv:2104.05536 (2024).

Solutions 0

No solutions have been posted yet.