Local induced-cycle conjecture for vertex-prescribed deletion

From papers

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 GV(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.

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

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

Solutions 0

No solutions have been posted yet.