Hong, Kang and Yu's induced-cycle connectivity conjecture

From papers

Let kk and ll be positive integers. Define a graph to be rr-connected if it remains connected after deletion of fewer than rr vertices. For a set XX of vertices, let GXG-X be the graph obtained by deleting XX, and let an induced cycle be a cycle with no edges between nonconsecutive vertices on the cycle. A set XX is incident with an edge ee if one of the endpoints of ee belongs to XX.

Hong–Kang–Yu conjecture. There exists a smallest positive integer g(k,l)g(k,l) such that, for every g(k,l)g(k,l)-connected graph GG, every edge eotinE(G[X])e otin E(G[X]) with XeV(G)X e V(G) and X=k|X|=k, there is an induced cycle CC in GXG-X satisfying eotinE(C)e otin E(C) and GCG-C is ll-connected.

The conjecture asks for a uniform connectivity threshold guaranteeing a removable induced cycle while avoiding a prescribed set of vertices and preserving a prescribed edge condition. The surrounding text identifies it as a conjecture from Hong, Kang and Yu; no resolution is supplied here.

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

Xiying Du, Yanjia Li, Shijie Xie and Xingxing Yu, “Linkages and removable paths avoiding vertices”, arXiv:2303.12146 (2023).

Solutions 0

No solutions have been posted yet.