The six-fifths conjecture for 2-edge-connected multigraphs

At least 7 years old · documented by

Let G=(V,E)G=(V,E) be a graph, let

LP(G)={x∈[0,2]E:x(δ(S))≥2 for every ∅⊂S⊂V},\mathrm{LP}(G)=\left\{x\in[0,2]^E:x(\delta(S))\geq 2\text{ for every }\emptyset\subset S\subset V\right\},

and let a vector dominate a convex combination of 2-edge-connected multigraphs when it is componentwise at least the incidence vector of that convex combination.

Six-fifths conjecture. If x∈LP(G)x\in\mathrm{LP}(G), then 65x\frac{6}{5}x dominates a convex combination of 2-edge-connected multigraphs of GG. Equivalently,

α2ECLP≤65.\alpha^{\mathrm{LP}}_{\mathrm{2EC}}\leq \frac{6}{5}.

This conjecture is stated to be wide open. The paper records only 65≤α2ECLP≤32\frac{6}{5}\leq\alpha^{\mathrm{LP}}_{\mathrm{2EC}}\leq\frac{3}{2} in general, with progress for special classes such as half-integer points.

References

Primary source

Arash Haddadan and Alantha Newman, “Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes”, arXiv:1811.09906 (2021).

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.