Non-separating even cycles in highly connected graphs (Q653835): Difference between revisions

A set \(X \subset V(G)\) is \(k\)-non-separating in the graph \(G\) if the subgraph spanned by \(V(G) \setminus X\) is \(k\)-connected. \textit{C. Thomassen} [``The Erdős-Pósa property for odd cycles in graphs of large connectivity,'' Combinatorica 21, No.\,2, 321--333 (2001; Zbl 0989.05062)] conjectured there exists a function \(f\) such that for every natural number \(k\) if a graph \(G\) is \(f(k)\)-connected there is an odd cycle \(C\) in \(G\) such that \(V(G) \setminus V(C)\) is \(k\)-connected. Note that \textit{C. Thomassen} [``Nonseparating cycles in \(k\)-connected graphs,'' J. Graph Theory 5, 351--354 (1981; Zbl 0498.05044)] proves that conjecture if the parity condition on \(C\) is dropped. Here we can read some related results, namely: for any \(k\)-connected graph \(G\) with \(k \geq 5\), there is an even cycle \(C\) such that \(G \setminus V(C)\) is \((k-4)\)-connected. Moreover, if \(G\) does not contain \(K_4 \setminus \{e\}\), that is \(K_4\) minus an edge, then \(G \setminus V(C)\) can be \((k-3)\)-connected.