# Lovász Path Removal Conjecture

**Conjecture**There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.

It follows from a theorem of Tutte that any 3-connected graph contains a non-separating path connecting any two vertices, and consequently, . When , it was independently shown by Chen, Gould, and Yu [CGY] and Kriesell [K] that .

Anwering a conjecture of Kriesell, Kawarabayashi et al. [KLRW] proved the following weaker statement, in which one only removes the edges of the path.

**Theorem**There exists a function such that for every -connected graph and any two vertices and of , there exists an induced path with ends and such that is -connected.

## Bibliography

[CGY] G. Chen, R. Gould, X. Yu, Graph connectivity after path removal, Combinatorica 23 (2003) 185--203.

[KLRW] K. Kawarabayashi, O. Lee, B. Reed, and P. Wollan, A weaker version of Lovasz's path removal conjecture, Journal of Combinatorial Theory, Series B 98 (2008) 972--979.

[K] M. Kriesell, Induced paths in 5-connected graphs, J. of Graph Theory, 36 (2001), 52--58.

*[T] C. Thomassen, Graph decompositions with applications to subdivisions and path systems modulo k, J. of Graph Theory, 7 (1983), 261--271.

* indicates original appearance(s) of problem.