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

From papers

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

LP(G)={x[0,2]E:x(δ(S))2 for every SV},\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 xLP(G)x\in\mathrm{LP}(G), then 65x\frac{6}{5}x dominates a convex combination of 2-edge-connected multigraphs of GG. Equivalently,

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

This conjecture is stated to be wide open. The paper records only 65α2ECLP32\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.

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

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

Solutions 0

No solutions have been posted yet.