McCuaig–Ota conjecture on contractible sets in 3-connected graphs

From papers

Let GG be a 33-connected graph. A set WV(G)W\subset V(G) is contractible if G(W)G(W) is connected and GWG-W is 22-connected; a contractible set with kk vertices is called a kk-contractible set. McCuaig–Ota conjecture. For every kNk\in\mathbb{N}, there exists an integer nn such that every 33-connected graph GG on at least nn vertices has a kk-contractible set.

The conjecture asks whether sufficiently large 33-connected graphs always contain contractible sets of every prescribed finite size. The paper proves the assertion for k5k\geqslant 5 under the minimum-degree condition δ(G)[2k+13]+2\delta(G)\geqslant \left[\frac{2k+1}{3}\right]+2, while the unrestricted conjecture remains open in the supplied text.

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

Nikolai Karol, “Restriction on minimum degree in the contractible sets problem”, arXiv:2212.02079 (2026).

Additional references

2 papers in this index state this conjecture (2011–2022). The statement above is taken from the most recent of them; the others are arXiv:1101.2357.

Solutions 0

No solutions have been posted yet.