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

About 15 years old · traced to

Let GG be a 33-connected graph. A set W⊂V(G)W\subset V(G) is contractible if G(W)G(W) is connected and G−WG-W is 22-connected; a contractible set with kk vertices is called a kk-contractible set. McCuaig–Ota conjecture. For every k∈Nk\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 k⩾5k\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.

References

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.

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.