Lovász Path Removal Conjecture

Importance: Medium ✭✭
Author(s): Lovasz, Laszlo
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: fhavet
on: March 4th, 2013

\begin{conjecture} There is an integer-valued function $f(k)$ such that if $G$ is any $f(k)$-connected graph and $x$ and $y$ are any two vertices of $G$, then there exists an induced path $P$ with ends $x$ and $y$ such that $G-V(P)$ is $k$-connected. \end{conjecture}

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

Anwering a conjecture of Kriesell, Kawarabayashi et al. [KLRW] proved the following weaker statement, in which one only removes the edges of the path. \begin{theorem} There exists a function $f(k)$ such that for every $f(k)$-connected graph $G$ and any two vertices $x$ and $y$ of $G$, there exists an induced path $P$ with ends $x$ and $y$ such that $G\setminus E(P)$ is $k$-connected. \end{theorem} % You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}


[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.

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.