Local induced-cycle conjecture for vertex-prescribed deletion

About 15 years old · traced to

A graph is rr-connected if deleting fewer than rr vertices leaves it connected. An induced cycle is a cycle with no edges between nonconsecutive cycle vertices.

Vertex-prescribed induced-cycle conjecture. For every kk, there exists an h(k)h(k) such that for every vertex vv of every h(k)h(k)-connected graph GG, there exists an induced cycle CC containing vv such that G−V(C)G-V(C) is kk-connected.

This is a weaker local form of the high-connectivity-keeping cycle problem, while the corresponding edge-prescribed form is equivalent to the high-connectivity-keeping path conjecture. The source states that this problem is open.

References

Primary source

Matthias Kriesell, “Minimal Connectivity”, arXiv:1101.2357 (2011).

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.